0

我认为矩阵链乘法问题的（低效）递归过程可以是这样的（基于Cormen中给出的递归关系）：

MATRIX-CHAIN(i,j)
    if i == j
        return 0
    if i < j
        q = INF

        for k = i to j-1
            q = min (q, MATRIX-CHAIN(i,k) + MATRIX-CHAIN(k+1, j) + c)  
            //c = cost of multiplying two sub-matrices.

        return q

时间复杂度为：

T(n) = summation over k varying from i to j [T(k) + T(n-k)]

这里，n = 要相乘的矩阵数。

T(n) 的值是多少以及如何？

4

2 回答 2

1

这是http://en.wikipedia.org/wiki/Catalan_number

您可以将递归关系视为做括号。wiki 页面深入描述了如何获得公式。

于 2012-08-28T12:20:05.650 回答
0

This might help:

you only have to work out each matrix-chain once (and store its value).

start = anywhere between i and j

end = anywhere between start and j

k = anywhere between start and end

if we think of a number with all 0's apart from three 1's (which represent start, k, end)

this special number has j-i+1 digits.

e.g. if i = 3 and j = 6 we need 4 digits giving us the following options:

1101 (i=3, k=4, j=6)

1011 (i=3, k=5, j=6)

0111 (i=4, k=5, j=6)

1110 (i=3, k=4, j=5)

number of choices for i,j,k = Combinations(3, j-i+1)

this is n!/(k! * (n-k)!) = (j-i+1)! / (3! * (j-i+1-3)!)

于 2012-08-28T12:28:57.663 回答