动态规划分析矩阵链顺序

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）。