アルゴリズムの計算量補足資料

アルゴリズムの計算量補足資料
「オーダ」ってのは何なのか
講義「アルゴリズムとデータ構造」配付資料: 井上康介
例えば，ソート法を計算量に基づいて分類するのなら，
1 計算量の考え方の基本
直接選択法，バブル・ソート，シェーカー・ソート，基本挿入
法はそれぞれ，実際には微妙に計算時間が異なるものの，
(時間) 計算量は，処理にかかる時間を「繰り返し回数」
n に対する計算時間の増加の仕方は二次関数 an2 + bn + c
に基づいて評価する．手順一つ一つを実施するためにコ
で表現できるので，すべて同じクラス O(n2 ) に分類でき
ンピュータは一定の時間を使うものであり，全体的にか
る．一方で，シェル・ソートは O(n1.25 ) という特殊なク
かる時間はその繰り返し回数に比例するからである．例
ラスであり，クイック・ソート，ヒープ・ソート，マージ・
えば課題 2 の問題 (n 個の点座標に対して，最短の 2 点間
ソートはすべて O(n log n) という，ソート法の中では最
距離を求める) では，n 個のデータに対して繰り返し回数
速のクラスに所属する (教科書 p.119)．
が n2 /2 − n/2 である．この繰り返し回数が，n が巨大に
なったときにどのような傾向を持って増えていくか (つま
り計算時間がどのような傾向を伴ってのびていくか) がこ
要点
こでの関心である．これを，計算量の漸近的な振る舞い
アルゴリズムの計算量は，計算時間がど
のような種類の関数 (例えば 2 次関数か，
3 次関数か，あるいは指数関数か，対数関
数か) に従って増えるかによって分類さ
れる．関数の種類を表現する方法がビッ
グ・オー表記である．
オーダとは，計算量の種別 (あるいは分
類) を示すものである．
(asymptotic behavior) と呼ぶ．
しかし，ここで問題となるのは，
「具体的な計算時間 (例
えば 530 [ms] とか) は，用いるコンピュータや OS に応じ
ていかようにでも変動しうる」ということである．すなわ
ち，細かい数字をいくら気にしても仕方がないのである．
ではどう考えるか？
2 計算量のクラス分け
具体的な計算時間そのものを評価するのではなく，n が
増加したときの計算時間の増加傾向を「どういう種類の
関数に従って増えるか」で評価しようとするのがビッグ・
オー表記 (big-oh notation) である．
n に関する 2 つの関数 f (n)，g(n) に対して，
f (n) ≤ c · g(n)
(n ≥ n0 )
を満足する定数 c，n0 が存在するとき，
「f (n) は g(n) の
オーダ (order) である」または「f (n) はオーダ g(n) であ
る」と表現され，
f (n) = O(g(n))
と書く．この意味は，
「n ≥ n0 において，f (n) は多くとも
g(n) の c 倍 (定数倍) にしかならない」ということである．
このような表現にして，この g(n) をできるだけ簡単な
関数にしてしまうことで，O 表記を使ってアルゴリズムの
計算量を分類することができる．
1

Download Report