動態規劃分析矩陣鏈順序

Question

所以我們有矩陣鏈順序算法，它可以找到乘法矩陣的最優方法。我明白爲什麼它的運行時間爲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）是顯而易見的，因爲有被嵌套，並運行爲O（n）倍三個環。我將如何去尋找大歐米茄（n^3）

Answer 1

爲了更好地理解問題，可以看看here。

您需要計算上方矩陣矩陣的元素。讓我們來看看這些子對角線：

1. 首先次對角，你只需要操作按照其元素，對角線具有N-1元素。

2. 您需要的第二個subidagonal ops並且它有n-2 elems。
   ...

3. 在過去的次對角需要N-1 OPS，它有 ELEM。

所以，你有一個總和I（N-1），0 <我<ñ。該總和可以分成兩部分：

• sum（in）= n（1 + 2 + ...（n-1））= n（n/2）（n-1）= n^3/2-n^2/2
• sum（i^2）= n（n + 1）（2n + 1）/ 6 = n^3/3 + n^2/2 + n/6

現在扣除，你將有n個^ 3/6 + ...

所以，這是歐米茄（N^3）。