這個樸素的代碼計算組合的大O複雜性是什麼？

以下遞歸算法是一個（相當低效的）的方式來計算Ñ選擇K：這個樸素的代碼計算組合的大O複雜性是什麼？

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); 
}

它是基於以下遞歸洞察：

enter image description here

實際評估此函數需要大量的函數調用。例如，計算2選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的函數，這個函數的大時間複雜度是什麼？

來源

2013-05-17 templatetypedef

你不應該返回'combinationOf（n-1，k-1）+ combinationsOf（n-1，k）'嗎？ – Blender

@ Blender-哦，哎呀！是的，修復。 :-) – templatetypedef

讓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)

如果我們除了擁有成本。然後，我們可以方便地查看

   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，內（外，我沒有看到整齊的公式）。

我們有明顯的上界獨立的k

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

，併爲k < n/2我們可以粗略估算

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

這給出了一個更小的界小k，所以總體

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

（需要c燈爲k爲最小值，因爲binom(n,k)減少回到1爲k > n/2）。

來源

2013-05-17 23:50:52

也許我錯過了一些東西，但是如果k> = n，那麼這個公式如何簡化爲2^{n + 1} - 1呢？如果k> = n，二項式定理表示總和減小到2^n，所以我們可以得到1 + 2（2^n）= 1 + 2^{n + 1}。標誌如何翻轉？ – templatetypedef

總和從「1」開始，而不是從「0」開始。我想我應該寫更好的'2 *Σbinom（n，j） - 1'，並且讓和從0開始。 –

非常漂亮！一個問題 - 這究竟是從哪裏來的？我通過感應工作，並檢查出來，但我不知道我會如何自己想出來。 – templatetypedef

O(2^n)

當n < k您在n步後按n = 0停止遞歸。在遞歸的每個級別中，您都調用兩個函數，所以這是數字2來自的地方。如果k = 0，則在「右分支」中的遞歸通過敲擊k = 0來停止，這是更少的步驟，然後敲擊n = 0，但總體複雜度仍然是2^n。

但真正的問題是遞歸本身 - 你會很快達到堆棧限制。

來源

2013-05-17 23:43:16 Strix

這個樸素的代碼計算組合的大O複雜性是什麼？

回答

相關問題