algorithm - 矩阵乘法的最佳括号

Question

语句是这样的（这种情况发生在选择所有矩阵对中的哪一个被括号括起来以获得最佳矩阵乘法时）

p(n) = Summation of P(k)P(k-n)是Ω(2^n)fork = 1和n - 1for 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 = 3 p(n) = 3和为了n = 4 p(n) = 5

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

Answer 1

p(n)是加泰罗尼亚数 =(2n choose n)/(n+1)并且是Theta(4^n/n sqrt(n))（使用斯特林公式），所以是Omega(2^n)。

您无法仅Omega(2^n)通过检查两个值来确定函数是否存在！

由于与实际的 theta 值相比，您正在寻找的界限是如此微弱，因此可能有一个更简单的证明。