経験的な成長のオーダー
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/09/13 15:58 UTC 版)
「アルゴリズム解析」の記事における「経験的な成長のオーダー」の解説
実行時間が ≈ k na という法則に従うと仮定し、2つの入力サイズ { n 1 , n 2 } {\displaystyle \{n1,n2\}} における実測値 { t 1 , t 2 } {\displaystyle \{t1,t2\}} から係数 a を求めるとすると、 t 2 / t 1 = ( n 2 / n 1 ) a {\displaystyle t_{2}/t_{1}=(n_{2}/n_{1})^{a}} という式が成り立つので a = log ( t 2 / t 1 ) / log ( n 2 / n 1 ) {\displaystyle a=\log(t_{2}/t_{1})/\log(n_{2}/n_{1})} となる。成長のオーダーがこの法則に従うなら、実測から得た a の値は異なる実測値同士から求めた場合も一定となるはずである。オーダーがその法則に従わないなら、a は一定にならない。それでも、このような比較は2つのアルゴリズムの「経験的な局所的成長オーダー」の挙動を比較するのに役立つ。先に挙げた表に適用してみると次のようになる。 n（リストの大きさ）コンピュータAの実行時間（ナノ秒単位）ローカルな成長オーダー(n^_)コンピュータBの実行時間（ナノ秒単位）ローカルな成長オーダー(n^_)15 7 100,000 65 32 1.04 150,000 0.28 250 125 1.01 200,000 0.21 1,000 500 1.00 250,000 0.16 ... ... ... 1,000,000 500,000 1.00 500,000 0.10 4,000,000 2,000,000 1.00 550,000 0.07 16,000,000 8,000,000 1.00 600,000 0.06 ... ... ... コンピュータAのアルゴリズムはこの法則に従って線型オーダーの成長を示していることが明らかである。コンピュータBでは a が急速に小さくなっており、成長の法則が異なることを示唆している。また、局所的成長オーダーはBの方が小さい（すなわちアルゴリズムの効率がよい）ことが経験的に判明する。
※この「経験的な成長のオーダー」の解説は、「アルゴリズム解析」の解説の一部です。
「経験的な成長のオーダー」を含む「アルゴリズム解析」の記事については、「アルゴリズム解析」の概要を参照ください。
- 経験的な成長のオーダーのページへのリンク
