アルゴリズムクイックリファレンス 第2版

■

395

付録

A

 

ベンチマーク

本書では、アルゴリズムの振る舞いについての性能データをそれぞれの項目で示

している。正確な性能結果を得るためには正しいベンチマークを使うことが重要な

ので、この付録では、アルゴリズムの性能を評価するための本書での基盤について

述べる。これは、本書の方式の正当性に対する読者の質問や疑問に答えるという点

でも有用だろう。実験データを計算する適切な手段を説明するので、読者の皆さん

には結果が正しいことを検証し、アルゴリズムが使われる目的での文脈で仮定が適

切なことを理解してもらえるはずだ。

アルゴリズム分析には多数の方法がある。

2

章では理論的かつ形式的にアプロー

チし、最悪時および平均時の分析という概念を紹介した。これらの理論的結果は実

験的に評価できるが、常に可能とは限らない。例えば、

20

個の数を整列するアルゴ

リズムの性能評価を考えよう。この

20

個の数値には、

2.43*10

18

個の置換があり、

平均時の性能を計算するために、それらすべてを評価するのは無理だ。さらに、こ

れらのすべての置換の整列時間を測っただけでは、平均を計算することもできない。

アルゴリズムの期待される性能時間を適切に計算できているかは、統計的手法を用

いて裏付けるしかない。

A.1

 統計の基礎

本章では、アルゴリズムの性能評価の本質的な点に絞って述べる。興味を持った

読者は、たくさんある統計の教科書から適当に選んで、実験計測を行うために本書

で用いた統計関連情報を調べるとよい

＊

1

。

アルゴリズムの性能を計算するために ...