algorithm - 动态规划Matrix-Chain-Order分析

Question

所以我们有了矩阵链序算法，它可以找到乘法矩阵的最佳方式。我明白为什么它会有 O(n^3) 的运行时间，但无法证明它的 big-Omega(n^3)。算法如下算法 Matrix-Chain-Order(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) 次。我将如何找到 big-Omega(n^3)

Answer 1

为了更好地理解问题，可以查看 here .

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

1. 第一个次对角线，每个元素只需要 1 操作，对角线有 n-1 个元素。

2. 第二个次斜面你需要 2 次操作，它有 n-2 个元素。
   ...

3. 对于最后一个次对角线，您需要 n-1 次操作，它有 1 个元素。

因此，对于 0 < i < n，您有一个求和 i(n-i)。这个总结可以分为两部分:

• 总和(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+...

所以，它是 Omega(n^3)。