5

次の再帰アルゴリズムは、n を計算して k を選択する (かなり非効率的な) 方法です。

 int combinationsOf(int n, int k) {
     if (k == 0) return 1;
     if (n == 0) return 0;
     return combinationsOf(n - 1, k) + combinationsOf(n - 1, k - 1);
}

これは、次の再帰的な洞察に基づいています。

ここに画像の説明を入力

ここに画像の説明を入力

ここに画像の説明を入力

実際にこの関数を評価するには、多くの関数呼び出しが必要です。たとえば、この方法で 2 choose 2 を計算すると、次の呼び出しが行われます。

 combinationsOf(2, 2)
   |  |
   |  +- combinationsOf(1, 2)
   |       |  |
   |       |  +- combinationsOf(0, 2)
   |       |
   |       +-- combinationsOf(1, 1)
   |             |  |
   |             |  +- combinationsOf(0, 1)
   |             |
   |             +- combinationsOf(1, 0)
   +- combinationsOf(2, 1)
        |  |
        |  +- combinationsOf(2, 0)
        |
        +- combinationsOf(1, 1)
             |  |
             |  +- combinationsOf(0, 1)
             |
             +- combinationsOf(1, 0)

この関数の実行時間を改善する方法はたくさんあります - 動的計画法を使用したり、閉じた形式の式 nCk = n! を使用したりできます。/ (k! (n - k)!) などですが、この特定のアルゴリズムがどれほど非効率的であるかに興味があります。

n と k の関数として、この関数の時間複雑度はどれくらいですか?

4

2 に答える 2

5

そのようにC(n,k)計算するコストをbinom(n,k)

C(0,_) = 1
C(_,0) = 1

ベースケースとして。

再発は明らかに

C(n,k) = 1 + C(n-1,k-1) + C(n-1,k)

コストが 1 になるように加算すると、次のことを簡単に確認できます。

             k
C(n,k) = 2 * ∑ binom(n,j) - 1
            j=0

誘導によって。

したがって、k >= nの場合、コストは2^(n+1) - 1、C(n,n-1) = 2^(n+1)- 3、C(n,1) = 2*n+1ですC(n,2) = n*(n+1)+1(それ以上の公式はわかりません)。

明らかな上限があります

C(n,k) < 2^(n+1)

に依存せず、k大まかにk < n/2見積もることができる

C(n,k) <= 2*(k+1)*binom(n,k)

これは、 small の境界をはるかに小さくするkため、全体的に

C(n,k) ∈ O(min{(k+1)*binom(n,min(k, n/2)), 2^n})

( はを 1 に戻すkため、最小値をクランプする必要があります)。binom(n,k)k > n/2

于 2013-05-17T23:50:52.270 に答える
4 
O(2^n)

n<k の場合、n ステップ後に n=0 をヒットして再帰を停止します。再帰の各レベルで 2 つの関数を呼び出すので、ここから 2 という数字が生まれます。n>k の場合、「右側の分岐」での再帰は、n=0 より少ないステップである k=0 をヒットすることによって停止されますが、全体的な複雑さは依然として 2^n です。

しかし、本当の問題は再帰そのものです。すぐにスタック制限に達します。

于 2013-05-17T23:43:16.650 に答える