time-complexity - 以下函数的增长率是多少

Question

就大 O 表示法而言，以下函数的增长率是多少？

f (n) = Comb(1000,n) for n = 0,1,2,…


int Comb(int m, int n)
{
    int pracResult = 1;
    int i;

    if (m > n/2) m = n-m;

    for (i=1; i<= m; i++)
    {
        pracResult *= n-m+i;
        pracResult /= i;
        practicalCounter++;
    }

    return pracResult;

}

递归：

int combRecursive (int m, int n)
{
    recursiveCounter++;
    if (n == m) return 1;
    if (m == 1) return n;
    return combRecursive(n-1, m) + combRecursive(n-1, m-1);

}

我猜n^2？？？不过，我可能错了……我一直在努力弄清楚事情的效率如何……

提前谢谢你。

Answer 1

是O(1)。

根据定义，f(n) = O(g(n))如果存在一个c这样的所有n，f(n) <= c*g(n)

让c=Comb(1000,500)

对于所有n，Comb(1000, n) < c * 1。因此Comb(1000, n) = O(1)

Answer 2

对于 n = 1 到 2000，将有与 n 成比例的操作

对于所有 n > 2000，总操作数是恒定的。

因此函数复杂度为 O (1)

我必须告诉你，你必须读一些书。:)
Sahni 的数据结构和算法读起来很轻松。Knuth 的算法非常繁重，但却是最好的。