実行時間複雑性の評価
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/09/13 15:58 UTC 版)
「アルゴリズム解析」の記事における「実行時間複雑性の評価」の解説
与えられたアルゴリズムの最悪ケースの実行時間複雑性は、そのアルゴリズムの構造を調べ、いくつかの単純化仮定をすることで評価できることがある。次の擬似コードを見てみよう。 1 入力から正の整数 n を得る2 if n > 103 print "This might take a while..."4 for i = 1 to n5 for j = 1 to i6 print i * j7 print "Done!" 与えられたコンピュータはこのアルゴリズムの実行で使われる個々の命令の処理に何らかの離散時間かかるだろう。命令の処理にかかる時間は命令の種類やコンピュータの実装によって変化するが、決定論的に得られるものとする。ステップ1の動作にかかる時間を T1、ステップ2にかかる時間を T2 などとする。 上のアルゴリズムで、ステップ1、2、7はそれぞれ1回しか実行されない。最悪の場合、ステップ3も1回だけ実行される。したがって、ステップ1、2、3、7の実行にかかる時間は次のようになる。 T 1 + T 2 + T 3 + T 7 {\displaystyle T_{1}+T_{2}+T_{3}+T_{7}\,} ループになっているステップ4、5、6の評価には若干の巧妙さが必要となる。外側のループの条件であるステップ4は ( n + 1 ) 回実行され（ループの終了判定に追加のステップが必要であるため、実行回数は n 回ではなく n + 1 回となる）、T4( n + 1 ) という時間がかかることになる。一方内側のループのループ回数は i の値で決まり、それは 1 から n まで順次変化する。最初に外側のループを通ったとき、j の変化する範囲は 1 から 1 までである。内側のループを1回だけ通ると、ループ本体（ステップ6）にかかる時間は T6、内側ループの条件（ステップ5）にかかる時間は 2T5となる。外側のループの次の反復では、j は 1 から 2 まで変化する。内側のループは2回通るので、内側ループ本体（ステップ6）にかかる時間は 2T6、内側ループの条件（ステップ5）にかかる時間は 3T5 となる。 要するに、内側ループの本体にかかる時間は、次のような等差数列で表される。 T 6 + 2 T 6 + 3 T 6 + ⋯ + ( n − 1 ) T 6 + n T 6 {\displaystyle T_{6}+2T_{6}+3T_{6}+\cdots +(n-1)T_{6}+nT_{6}} この式は次のように因数分解できる。 T 6 [ 1 + 2 + 3 + ⋯ + ( n − 1 ) + n ] = T 6 [ 1 2 ( n 2 + n ) ] {\displaystyle T_{6}\left[1+2+3+\cdots +(n-1)+n\right]=T_{6}\left[{\frac {1}{2}}(n^{2}+n)\right]} 内側のループの条件部にかかる時間の総計も同様に次のように得られる。 2 T 5 + 3 T 5 + 4 T 5 + ⋯ + ( n − 1 ) T 5 + n T 5 + ( n + 1 ) T 5 {\displaystyle 2T_{5}+3T_{5}+4T_{5}+\cdots +(n-1)T_{5}+nT_{5}+(n+1)T_{5}} = T 5 + 2 T 5 + 3 T 5 + 4 T 5 + ⋯ + ( n − 1 ) T 5 + n T 5 + ( n + 1 ) T 5 − T 5 {\displaystyle =T_{5}+2T_{5}+3T_{5}+4T_{5}+\cdots +(n-1)T_{5}+nT_{5}+(n+1)T_{5}-T_{5}} これを因数分解すると次のようになる。 T 5 [ 1 + 2 + 3 + ⋯ + ( n − 1 ) + n + ( n + 1 ) ] − T 5 = T 5 [ 1 2 ( n 2 + 3 n + 2 ) ] − T 5 {\displaystyle T_{5}\left[1+2+3+\cdots +(n-1)+n+(n+1)\right]-T_{5}=T_{5}\left[{\frac {1}{2}}(n^{2}+3n+2)\right]-T_{5}} 以上からこのアルゴリズムにかかる時間の総和は次のようになる。 f ( n ) = T 1 + T 2 + T 3 + T 7 + ( n + 1 ) T 4 + [ 1 2 ( n 2 + n ) ] T 6 + [ 1 2 ( n 2 + 3 n + 2 ) ] T 5 − T 5 {\displaystyle f(n)=T_{1}+T_{2}+T_{3}+T_{7}+(n+1)T_{4}+\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n+2)\right]T_{5}-T_{5}} これを整理すると次のようになる。 f ( n ) = [ 1 2 ( n 2 + n ) ] T 6 + [ 1 2 ( n 2 + 3 n ) ] T 5 + ( n + 1 ) T 4 + T 1 + T 2 + T 3 + T 7 {\displaystyle f(n)=\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}} 経験的に最も次数の高い項が成長率を支配することが知られており、それが実行時間のオーダーを定義する。この例では n2 が最も次数が高いので、f(n) = O(n2) という結論が得られる。形式的には次のように証明される。 [ 1 2 ( n 2 + n ) ] T 6 + [ 1 2 ( n 2 + 3 n ) ] T 5 + ( n + 1 ) T 4 + T 1 + T 2 + T 3 + T 7 ≤ c n 2 , n ≥ n 0 {\displaystyle \left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},\ n\geq n_{0}} の証明 [ 1 2 ( n 2 + n ) ] T 6 + [ 1 2 ( n 2 + 3 n ) ] T 5 + ( n + 1 ) T 4 + T 1 + T 2 + T 3 + T 7 {\displaystyle \left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}} ≤ ( n 2 + n ) T 6 + ( n 2 + 3 n ) T 5 + ( n + 1 ) T 4 + T 1 + T 2 + T 3 + T 7 {\displaystyle \leq (n^{2}+n)T_{6}+(n^{2}+3n)T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}} （ここで n ≥ 0） k が [T1..T7] 以上の定数とすると T 6 ( n 2 + n ) + T 5 ( n 2 + 3 n ) + ( n + 1 ) T 4 + T 1 + T 2 + T 3 + T 7 ≤ k ( n 2 + n ) + k ( n 2 + 3 n ) + k n + 5 k {\displaystyle T_{6}(n^{2}+n)+T_{5}(n^{2}+3n)+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq k(n^{2}+n)+k(n^{2}+3n)+kn+5k} = 2 k n 2 + 5 k n + 5 k ≤ 2 k n 2 + 5 k n 2 + 5 k n 2 {\displaystyle =2kn^{2}+5kn+5k\leq 2kn^{2}+5kn^{2}+5kn^{2}} (for n ≥ 1) = 12 k n 2 {\displaystyle =12kn^{2}} したがって [ 1 2 ( n 2 + n ) ] T 6 + [ 1 2 ( n 2 + 3 n ) ] T 5 + ( n + 1 ) T 4 + T 1 + T 2 + T 3 + T 7 ≤ c n 2 , n ≥ n 0 {\displaystyle \left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},n\geq n_{0}} ここで c = 12 k , n 0 = 1 {\displaystyle c=12k,n_{0}=1} このアルゴリズムを解析するより洗練された手法としては、[T1..T7] をそれぞれの実際にかかる時間以上の単位時間と等しいと宣言する方法がある。その場合、このアルゴリズムの実行時間は次のようになる。 4 + ∑ i = 1 n i ≤ 4 + ∑ i = 1 n n = 4 + n 2 ≤ 5 n 2 {\displaystyle 4+\sum _{i=1}^{n}i\leq 4+\sum _{i=1}^{n}n=4+n^{2}\leq 5n^{2}} (for n ≥ 1) = O ( n 2 ) {\displaystyle =O(n^{2})}
※この「実行時間複雑性の評価」の解説は、「アルゴリズム解析」の解説の一部です。
「実行時間複雑性の評価」を含む「アルゴリズム解析」の記事については、「アルゴリズム解析」の概要を参照ください。
- 実行時間複雑性の評価のページへのリンク
