iT邦幫忙

0

Leetcode 1423 的時間複雜度問題

各位先進好
敝人在此網站找到Leetcode 1423的詳解:
https://blog.csdn.net/fuxuemingzhu/article/details/113729881
該網站所提供的解法我都可理解,但為何第一種使用recursion的解法時間複雜度為O(N * k)呢? 要如何分析?

麻煩站內熱心的邦友解惑了,謝謝!

1 個回答

1
最佳解答

第一種寫法的時間複雜度應該是 O(2^k)

不過只有一個變量的話還是習慣寫成 O(2^n)


下面的結果是遞迴中 i, j, k 的變化

  • 假設 n=[1,2,1]、k=2
0 2 2
1 2 1
2 2 0
1 1 0
0 1 1
1 1 0
0 0 0
  • 假設 n=[1,2,2,1]、k=2
0 3 2
1 3 1
2 3 0
1 2 0
0 2 1
1 2 0
0 1 0

可以發現,時間複雜度只和 k 有關


接著加大 k=3

0 3 3
1 3 2
2 3 1
3 3 0
2 2 0
1 2 1
2 2 0
1 1 0
0 2 2
1 2 1
2 2 0
1 1 0
0 1 1
1 1 0
0 0 0

可以發現 k=3 的每個數字都比 k=2 多一倍
繼續加大 k=4 又會比 k=3 多一倍
所以這是一種 2 的次方關係

ffaanngg iT邦新手 5 級 ‧ 2021-03-12 01:37:29 檢舉

感謝回答
k=2時,計算的次數是 2+4
k=3時,計算的次數是 2+4+8
因此依等比級數公式,計算次數為2 * (2^k-1),是O(2^k)沒錯

不過不知為何不少大陸人的部落格都寫O(N * k)

作者的解釋是計算所有組合,但感覺和實際情況有落差
我也不是很理解這段話的意思。

我要發表回答

立即登入回答