algorithm - 此关系的时间复杂度 - 矩阵链乘法

Question

我认为矩阵链乘法问题的(低效)递归过程可以是这样的(基于 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) = 从 i 到 j 的 k 求和 [T(k) + T(n-k)]

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

T(n) 的值是多少？如何计算？

Answer 1

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

你可以把递归关系看成做括号。维基页面详细描述了如何得出公式。