アルゴリズム解析
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}}
経験的に最も次数の高い項が成長率を支配することが知られており、それが実行時間のオーダーを定義する。この例では n が最も次数が高いので、f(n) = O(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 ≤ 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}}
アルゴリズム解析(アルゴリズムかいせき)とは、アルゴリズムの実行に必要とされるリソース(時間や記憶領域)量を見積もることである。多くのアルゴリズムは任意長の入力を受け付けるよう設計されている。アルゴリズムの「効率」や「複雑さ」は一般に、入力長からそのアルゴリズムを実行するのに必要なステップ数(時間複雑性)や記憶領域サイズ(空間複雑性)への関数として表される。
アルゴリズム解析は計算複雑性理論の重要な一分野である。計算複雑性理論では、与えられた計算問題を解くアルゴリズムが必要とするリソースを理論的に見積もる。この見積もりにより効率的なアルゴリズムを設計する指針が得られることがある。
アルゴリズム解析ではふつう、漸近的(asymptotic)な意味で複雑性を見積もる。すなわち、ある程度大きな入力長の際の複雑性関数を見積もる。このためにO記法、Ω記法、Θ記法が用いられる。
= 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}}
これを整理すると次のようになる。
したがって [ 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})}