动态规划Matrix-Chain-Order分析
analysis of dynamic programming Matrix-Chain-Order
所以我们有了矩阵链序算法，它可以找到乘法矩阵的最佳方式。我明白为什么它会有 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)
为了更好地理解问题，可以查看 here。
您需要计算上三角矩阵的元素。让我们看看这些次对角线：
- 第一个次对角线，每个元素只需要1次操作，对角线有n-1个元素。
你需要 2 ops 并且它有 n-2 元素。
...
对于最后一个次对角线你需要 n-1 ops 并且它有 1 elem。
因此，对于 0 < i < n，您有一个求和 i(n-i)。这个总和可以分为两部分：
- 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+...
所以，它是 Omega(n^3)。
所以我们有了矩阵链序算法，它可以找到乘法矩阵的最佳方式。我明白为什么它会有 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)
为了更好地理解问题，可以查看 here。
您需要计算上三角矩阵的元素。让我们看看这些次对角线：
- 第一个次对角线，每个元素只需要1次操作，对角线有n-1个元素。
你需要 2 ops 并且它有 n-2 元素。
...对于最后一个次对角线你需要 n-1 ops 并且它有 1 elem。
因此，对于 0 < i < n，您有一个求和 i(n-i)。这个总和可以分为两部分：
- 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+...
所以，它是 Omega(n^3)。