矩阵链乘法的时间复杂度

Question

这是Cormen等人在"算法导论"中解决的问题.人.CH.15,第15.2节:矩阵链乘法.PG.373.

目标是将矩阵链产品A1.A2.A3括号括号,使得存在最小数量的标量乘法.
对于Ai.Ai + 1 .... Ak.Ak + 1 ..... Aj,
Matrix 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

(m [i,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)对于完整的解决方案.