1. ホーム
  2. performance

[解決済み] nの漸近成長でfloor(n/2)を選択する。

2022-03-07 19:47:17

質問

n の漸近成長はどのように floor(n/2) を選べばよいのでしょうか? 私は に等しいことがわかりました。

[n*(n-1)*........*(floor(n/2)+1)] / (n-floor(n/2))!

どうすればいいのでしょうか? 答えよりもヒントが欲しいのです。

解決方法は?

使用方法 スターリングの近似式 となります。

n! = \sqrt{2n\pi}(n/e)^n

これを $choose{n}{n/2}$ に代入すると、最終的に以下のようになります。

2^{n+1/2}/\sqrt{n\pi}

PS.実際に答えを使う前に、私の計算を確認した方がいいかもしれませんね :-)