ダイナミックプログラミングの解析Matrix-Chain-Order

Question

行列を掛け合わせる際に最適な方法を見つけるMatrix Chain Orderアルゴリズムがあります。なぜそれがO（n^3）の実行時間を持つが、その大きなオメガ（n^3）を証明するのに問題があるのか​​分かります。アルゴリズムは アルゴリズムマトリックスチェーン・オーダ（P）

1. n ← p.length − 1 
2. for i ← 1 to n do 
3. m[i, i] ← 0 
4. for l ← 2 to n do 
5. for i ← 1 to n − l + 1 do 
6.  j ← i + l − 1 
7.  m[i, j] ← ∞ 
8.  for k ← i to j − 1 do 
9.  q ← m[i, k] + m[k + 1, j] + pi−1pkpj (these are P(base)i-1 
10.  if q < m[i, j] then 
11.   m[i, j] ← q 
12.   s[i, j] ← k 
13. return s 

はO（n^3）の下でネストされたと（N）回Oを実行している3つのループがあるので、明らかです。どのように私は大きなオメガ（n^3）を見つけることになるでしょうか？

Answer 1

質問を理解するにはhereがあります。

上位の矩形行列の要素を計算する必要があります。これらの副対角を見てみましょう：

1. まず副対、あなたはその要素ごとにのみ操作を必要とし、対角線がのn-1要素を持っています。

2. 第2次対角には opsが必要です。n-2 elemsがあります。あなたはのn-1 OPSを必要とし、それがのelemを持って、最後の副対角については
   ...

3. 。だから、

、あなたは0 <私は< nに、合計I（N-i）を持っています。この総和は、2つの部分に分割することができる：

• 合計n（1 + 2 + ...（n-1））= n（n/2）（n-1）= n^（n + 1）（2n + 1）/ 6 = n^3/3 + n^2/2 + n/6

は今引くと、あなたは、n^3/6 + ...

だから、それはオメガである（nは^ 3）があります。