アルゴリズム解析
与えられたアルゴリズムの最悪ケースの実行時間複雑性は、そのアルゴリズムの構造を調べ、いくつかの単純化仮定をすることで評価できることがある。次の擬似コードを見てみよう。
与えられたコンピュータはこのアルゴリズムの実行で使われる個々の命令の処理に何らかの離散時間かかるだろう。命令の処理にかかる時間は命令の種類やコンピュータの実装によって変化するが、決定論的に得られるものとする。ステップ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となる。
≤ ( 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}}