动态规划矩阵链阶分析

Question

因此，我们有矩阵链序算法，它找到了矩阵乘的最优方法。我明白为什么它的运行时间为O(n^3)，但很难证明它的大-Omega(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

为了更好地理解问题，你可以看上去像这里。

你需要计算上方阵的元素。让我们看看这些次对角线：

1. 第一个次对角线，每个元素只需要1操作，而对角线有n-1元素。
2. 其次，你需要，2，，ops，它有，n-2，等元素. ..。
3. 对于最后一个次对角线，您需要n-1操作，并且它有1 elem。

因此，您有一个求和i( n )，对于0

• 和(In)=n(1+2+.(n-1))= n(n/2)(n-1) = n^3/2-n^2/2
• 和(i^2)= n(n+1)(2n+1)/6 = n^3/3+n^2/2+n/6

现在减去n^3/6+.

所以，它是欧米茄(n^3)。