最小乘数，使用遍历的方法和使用使用递归的方法那个更加效率一些

Which is a more efficient way to determine the optimal number of multiplications in a matrix-chain multiplication problem: enumerating all the ways of parenthesizing the product and computing the number of multiplications for each, or running RECURSIVE-MATRIX-CHAIN? Justify your answer.

定义遍历使用时间的函数为 T(n) = sigma(1..n-1):T(k)T(n-k)，

定义递归使用时间的函数为T1(n)，

T1(n) = 1 + sigma(1..n-1):sigma(2..n):sigma(i..j-1):(T(k) + T(n-k) + 1)

<>

< 1 + s(1..n-1):s(2..n):s(1..n-1):T(k) + s(1..n-1):s(2..n):s(1..n-1):T(n -k) + n*n*n

< 1 + 2n*n*s(1..n-1):T(k) + n*n*n

根据之前的证明，知道T(n)=Ω(2ⁿ)。于是有 T(n-k) > 2^{n-k >}2*n*n，

于是有2 *n*n*s(1..n-1):T(k) = s(1..n-1):2n*n*T(k) <　s(1..n-1):T(n-k)T(k)，同时n*n*n是2ⁿ

^{的低阶，即T(n)的低阶，可以忽略．}

^{根据以上的推导，我觉得递归的方法相对更效率．为什么？到底省掉了哪些部分？}