矩阵链乘法的注解

Question

这里是回忆录版矩阵链乘法程序的程序，从介绍到算法，由cormen等。

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]

在描述中提到了这一点，因为我们可以将查找链的调用分为两种类型：

调用其中的mi，j=无穷，因此第3-9行是executed.

• calls，其中mi，j小于无穷，因此查找链在

中返回。

有n个第一类型的平方调用，每个表条目一个。第二类型的所有调用都是由第一种类型的调用作为递归调用进行的。每当给定的查找链调用进行递归调用时，它都会对它们进行"n“调用。因此，共有第二种类型的n个多维数据集调用。第二种类型的每次调用都需要O(1)时间，而第一种类型的每一次调用都需要O(n)时间加上递归调用中所花费的时间。总时间是O(n立方体)。

我的问题是

1. 作者所说的“第二种类型的所有调用都是按第一种类型的调用进行的递归调用”是什么意思？
2. 如何想出“给定的查找链调用”来进行递归调用，在上面的句子中对它们进行"n“？

。

谢谢!

Answer 1

1. --我认为它们的意思是，如果考虑递归调用树，第二种类型的调用将显示为叶(不再是递归的)，而第一种类型的调用是树的内部节点。第二种类型是由第一种类型调用的。
2. -- LOOKUP-CHAIN第5行中的for循环最多执行n次迭代(因为1≤i≤j≤n)，以弥补2n=O(n)递归调用。

如果您将这种递归算法描绘为一棵树，那么它的复杂性可能会更容易理解：

内部节点对应于“类型2"，不超过n平方(因为回忆录)，每个节点执行O(n) operations

• The叶对应于”类型1“。因为最多有n个内节点，最多有2n个子节点，所以您的叶子不能超过2n个，并且每个节点都执行

的θ(1)操作。