0

Big 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を推測しますか？私はおそらく間違っています...私はいつも物事がどれほど効率的であるかを理解するのに苦労してきました...

よろしくお願いします。

4

2 に答える 2

0

ですO(1)。

定義上、すべての人にそのようなものf(n) = O(g(n))が存在する場合、cnf(n) <= c*g(n)

= c_Comb(1000,500)

すべてのためnに、Comb(1000, n) < c * 1。したがって、Comb(1000, n) = O(1)

于 2013-03-09T05:35:08.780 に答える
0

n = 1〜2000の場合、nに比例する演算があります

すべてのn>2000の場合、合計操作は一定です。

したがって、関数の複雑さはO（1）です。

そして、私はあなたがいくつかの本を読まなければならないことをあなたに言わなければなりません。:) Sahni
によるデータ構造とアルゴリズムは非常に簡単に読み取れます。Knuthによるアルゴリズムは非常に重いですが、最高のものの1つです。

于 2013-03-09T05:35:57.860 に答える