プログラミング作法 第２章 アルゴリズムとデータ構造 ２．５ Ｏ記法

アルゴリズムの実行時間と領域の必要量を、プログラミング言語やコンパイラ、マシンアーキテクチャ、プロセッサ速度、システム負荷その他の複雑なファクタから切り離して比較したいからだ。
　そのために「Ｏ記法(Ｏ-notation)」という標準記法が存在する。これの基本パラメータは具体的な問題のサイズを表すｎであり、計算量(complexity)つまり実行時間はｎの関数として表現される。「二分探索はＯ(logn)である、すなわち項目数ｎの配列を探索するのにlognオーダーのステップが必要になる」というように、"Ｏ"はオーダー(order)を表す。Ｏ(f(n))という表記は、ｎが十分に大きければ、たとえばＯ(n^2)あるいはＯ(nlogn)のように、実行時間は最大でf(n)に比例するという意味になる。

もっとも重要なケースを次に挙げておこう

記法	名称	例
-----------	-------	----------------
Ｏ(1)	定数	配列インデックス
Ｏ(logn)	対数	二分探索
Ｏ(n)	１次	文字列比較
Ｏ(nlogn)	nlogn	クイックソート
Ｏ(n^2)	２次	単純なソート手法
Ｏ(n^3)	３次	行列乗算
Ｏ(2^n)	指数	集合分割問題

問題２−３
クイックソートが最悪の振る舞いを見せる場合は、ピボット値を常に最大(最小)値を選び続けた場合が想定できる。動作の測定を行うプロセスを自動化するプロセスは、Cならばqsortの比較関数が呼びされた回数をカウントできるようにすれば良いと思う。開発環境がインストールできたならば試してみよう。これは宿題。
問題２−４
低速なソートといえばバブルソートが思いつく。これも計算量の測定をしようと思うなら、比較して値をいれかえる関数をカウントできるようにすれば良いと思う。これも宿題にしておく。