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)!在使用大 O 表示法时忽略，所以我们得到O((n + r - 1)! / n!). 我想这可能是家庭作业，所以试着自己从这里走得更远。可以简化(n + r - 1)! / n!为一个非常简单的表达式，因为它在 a 内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))