時間遞歸算法的複雜性

Question

每當我看到一個遞歸解決方案，或者我爲一個問題編寫遞歸代碼時，我很難弄清楚時間複雜度，在大多數情況下，我只是說它的指數？它是如何實際指數？人們怎麼說它是2^n，什麼時候是n！，什麼時候是n^n或n^k。

我心中有一個疑問 -

1. 讓的說找到一個字符串的所有排列
2. 找到一個數組到k其總結（指數所有序列，如何（O（N）！）我的確切計算）。
3. 找到總和爲0的k大小的所有子集（k會出現在複雜性的某處，它應該是正確的？）。

可以any1幫助我如何計算這些問題的確切複雜性，我能夠爲他們編寫代碼，但它很難理解確切的時間複雜性。

Answer 1

找到所有在數組中總和爲k的序列（指數，我如何計算）。

設F(a, n, k)是S ⊂ {0, 1, ..., n-1}所有子集的數量，以便

∑ a[i] == k 
i∈S 

然後我們就可以通過在兩個子問題（爲n > 0）分裂問題計算F(array, length of array, k)遞歸。

{0, 1, ..., n-1}的子集可以分爲兩類，那些包含n-1，而那些不包含那些。

我們得到遞歸

F(a,n,k) = F(a,n-1,k) + F(a,n-1, k-a[n-1]) 

讓T(n)是計算F(_,n,_)所需的時間（下劃線表示T(n)不僅取決於n，而不是在陣列上或k [儘管對於特定陣列和k [F然後立即暗示

T(n) = 2 * T(n-1) 

爲n > 0。

爲n == 0，我們可以計算在固定時間的解決方案，

F(a, 0, k) = k == 0 ? 1 : 0 

所以我們必須T(n) = 2^n * T(0)電感。

如果子集不應只進行計數，但輸出的複雜度變O(n * 2^n)並且結合是緊密的（對於所有0組成的數組，與k == 0，所有子集滿足條件，並打印它們需要Θ(n * 2^n)時間） 。

查找所有總和爲0的k大小的子集（k會出現在複雜性的某處，它應該是正確的？）。

是的，這個問題的複雜性取決於n和k。

讓F(a,n,k,s)是基數的子集S ⊂ {0, 1, ..., n-1}k這樣

∑ a[i] == s 
i∈S 

對於k == 0，我們再有一個固定的時間回答的數目，有這樣的一個子集（空集），如果s == 0，並沒有除此以外。對於k > n設置{0, 1, ..., n-1}沒有基數k的子集，所以F(a,n,k,s) = 0如果k > n。

如果0 < k <= n，我們可以像上面，考慮含n-1子集和那些單獨不這樣做，給

F(a,n,k,s) = F(a,n-1,k,s) + F(a,n-1,k-1,s - a[n-1]) 

和時間複雜度，我們發現

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

這遞歸從二項係數可知，我們有

T(n,k) = n `choose` k = n!/(k! * (n-k)!) 

（與T(n,0) = 1）。

再次，如果套不得纔算得上，但輸出的時間複雜度的增加，這裏所有集合有基數k，因此它成爲

k * n!/(k! * (n-k)!) 

Answer 2

看看Master Theorem。這在教授完全解釋。 Tim Roughgarden的Algorithms: Design and Analysis: Part I，來自斯坦福大學。這是我推薦的在線課程，但您可以在沒有註冊課程的情況下觀看視頻。如果您有興趣，還有本課程的第二部分。