algorithm - ステップ C(n+r-1, r-1) のアルゴリズムの複雑さについて

Question

アルゴリズムが問題を解決するために C(n+r-1, r-1) ステップを必要とする場合 (n は入力数、r は定数)、アルゴリズムのステップは指数関数的成長を考慮しますか?</p>

Answer 1

Cが二項係数関数であると仮定しますC(n + r - 1, r - 1) = (n + r - 1)! / ((r - 1)! * n!)。rは定数なので(r - 1)!、big-O 表記を使用する場合は無視できるため、 が得られO((n + r - 1)! / n!)ます。これは宿題かもしれないと思うので、自分でここから先に進んでみてください。(n + r - 1)! / n!の内部にあるため、非常に単純な式に還元することができ、O()指数関数であるかどうかを簡単に確認できます。(ヒント: には因子がいくつあり(n + r - 1)! / n!ますか?)

Answer 2

いいえ、複雑さO(n^(r-1))は、指数関数的成長ではなく（そしてそれよりも優れた）多項式成長です。

let g(n) = C(n+r-1, r-1) 
         = (n+r-1)! / ((r-1)!n!)  
         = (n+1)(n+2)...(n+r-2)(n+r-1) / (r-1)!
         = n^(r-1) + kn^(r-2) + k'n^(r-3)... k''n + k''' / (r-1)!

it's easy to say that k,k'...k'',k'''and (r-1)! are all constant,
so T(g(n)) = O(n^(r-1))