矩阵链乘法的时间复杂度

Question

这是科门等人在“算法导论”中解决的问题。阿尔。Ch.15，第15.2节:矩阵链乘法。Pg。373.

其目的是将矩阵链乘积A1.A2.A3.....An括起来，使标量乘法的数目最小。

对于Ai.Ai+1....Ak.Ak+1.....Aj，

矩阵Ai的维数为pi-1xpi，给出了递归算法。

m[i,j] = 0 if i=j
       = min {m[i,k] + m[k+1] + pi-1.pk.pj}   where i goes from k to (j-1)   if i<j

(mi，j是乘积Ai....Aj所需的最小标量乘法数)

到目前为止，我明白了，但他说的时间复杂性是O(n^3)。

当我看伪代码时，有3个for循环，所以它是正确的。但我不能直观地理解递归。

有人能帮忙吗？

Answer 1

最后的解决方案是计算m[0,N]。但是，在计算m[i,j]之前，需要计算所有m[0,N]值。这使得它成为O(N^2)。

从递归公式中可以看到，每个m[i,j]计算都需要O(N)复杂性。

因此，O(N^3)用于完整的解决方案。

Answer 2

对于任何给定的MCM问题，都可能存在O(n^2)唯一的子问题，对于每一个这样的子问题，都可能存在O(n)分裂。

所以它是O(n^3)。