algorithm - 矩阵链乘法的内存版本

Question

这里是 cormen 等人的 Introduction to Algorithms 的 memoized version matrix chain multiplication 程序的程序

MEMOIZED-MATRIX-CHAIN(p)

1 n  length[p] - 1   
2 for i = 1 to n
3      do for j = i to n
4             do m[i, j]  = infinity   
5 return LOOKUP-CHAIN(p, 1, n)

LOOKUP-CHAIN(p, i, j)

1 if m[i,j] < infinity
2    then return m[i, j]
3 if i = j
4    then m[i, j]  0
5    else for k =  i to j - 1
6             do q = LOOKUP-CHAIN(p, i, k) +
                     LOOKUP-CHAIN(p, k + 1, j) +
                     p(i - 1)* p(k) *p(j) 
7                if q < m[i, j]
8                   then m[i, j] = q
9 return m[i, j]

在描述中提到它是因为我们可以将 LOOKUP-CHAIN 的调用分为两种类型:

1. 调用其中 m[i,j] = infinity，以便执行第 3-9 行。
2. 调用其中 m[i,j] 小于无穷大，因此 LOOKUP-CHAIN 简单地返回行

有 n 个第一种类型的方形调用，每个表条目一个。第二种类型的所有调用都是第一种类型调用的递归调用。每当给定的 LOOKUP-CHAIN 调用进行递归调用时，它都会进行“n”次递归调用。因此，总共有 n 个第二类立方体调用。每次调用第二种类型需要 O(1) 时间，第一种类型的每次调用都需要 O(n) 时间加上递归调用所花费的时间。总时间是 O(n 立方体)。

我的问题是

1. 作者所说的“所有第二种类型的调用都是第一种类型的调用的递归调用”是什么意思？
2. 作者如何在上面的句子中提出“给定的 LOOKUP-CHAIN 调用进行递归调用，它进行了“n”次递归调用”？

谢谢!

Answer 1

1. 我认为它们的意思是，如果您考虑递归调用树，第二种类型的调用显示为叶子(不再递归)，而第一种类型的调用是树的内部节点。所以是的，第二种类型被第一种类型调用。

2. LOOKUP-CHAIN第5行的for循环最多执行n次迭代(因为1≤i≤j≤n)所以可以弥补到 2n=O(n) 次递归调用。

如果你把它想象成一棵树，也许更容易理解这个递归算法的复杂性:

• 内层节点对应“type 2”，不能超过n²(因为有memoization)，每一个执行O(n)次操作

• 叶子对应于“类型 1”。因为最多有 n² 个内部节点和最多 2n 个 child ，所以你不能有超过 2n³ 个叶子，并且每个叶子都执行 θ(1) 操作