的矩阵乘法

Question

声明最佳括号去这样

p(n) = Summation of P(k)P(k-n)是Ω(2^n)为k = 1到n - 1和n> = 2（而选择其中所有的基质对被括号最佳矩阵乘法发生这种情况）。

p(n)是备用括号的组合数。

说p(3) = A1(A2*A3)或(A1*A2)A3或(A1*A2*A3)。

k：拆分值。

n：矩阵的数量。

我用递归方法解决了这个方程。

可以说我有四个矩阵A1,A2,A3,A4。

比方说k = 2，我们有n = 4。

p(4) = p(1)p(3) + p(2)p(2)

解决递归p(3)和p(2)我们得到：

p(4) = p(1)p(3) + p(2)p(2) + p(1)p(1)p(2) + p(1)p(2)p(1) + p(1)p(1)p(1)p(1)。

它意味着什么，是我们可以通过以下方式圆括号A1A2A3A4：

p(4) = A1(A2A3A4)或(A1A2)(A3A4)或(A1)(A2)(A3A4)或(A1)(A2A3)(A4)或(A1)(A2)(A3)(A4)。

我的问题是：

如果n = 3p(n) = 3和n = 4p(n) = 5

那么怎么来p(n) = summation of p(k)p(n-k)是Ω(2^n)？

Answer 1

p(n)是Catalan数= (2n choose n)/(n+1)那就是Theta(4^n/n sqrt(n))（使用Stirling公式）等是Omega(2^n)。

通过检查两个值，您无法确定函数是否为Omega(2^n)！

由于您正在寻找的边界与实际的θ值相比非常弱，因此可能有一个更简单的证明。