algorithm - 行列の掛け算に最適な括弧

Question

ステートメントは次のようになります (このシナリオは、行列の乗算を最適化するために、すべての行列のペアのどれを括弧で囲むかを選択するときに発生します)

p(n) = Summation of P(k)P(k-n)はtoと forΩ(2^n)です。k = 1n - 1n> = 2

p(n)交互括弧の組み合わせの数です。

p(3) = A1(A2*A3)または(A1*A2)A3または と言い(A1*A2*A3)ます。

k: 分割値。

n: 行列の数。

この方程式を再帰を使って解きました。

4 つの行列があるとし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)2 つの値を調べるだけでは、関数が であるかどうかを判断することはできません!

あなたが求めている境界は実際のシータ値と比較して非常に弱いので、おそらくもっと簡単な証明があります.