各位先進好
敝人在此網站找到Leetcode 1423的詳解：
https://blog.csdn.net/fuxuemingzhu/article/details/113729881
該網站所提供的解法我都可理解，但為何第一種使用recursion的解法時間複雜度為O(N * k)呢？ 要如何分析？
麻煩站內熱心的邦友解惑了，謝謝!
已邀請的邦友 {{ invite_list.length }}/5
第一種寫法的時間複雜度應該是 O(2^k)
不過只有一個變量的話還是習慣寫成 O(2^n)
下面的結果是遞迴中 i, j, k 的變化
0 2 2
1 2 1
2 2 0
1 1 0
0 1 1
1 1 0
0 0 0
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 的次方關係
iThome鐵人賽
看影片追技術