我做了一個程式來尋找一個長度為K的陣列的所有子集。 我很難找到它的時間復雜性，因為遞回呼叫是在一個for回圈中進行的。
我認為這不是θ，因為程式可以終止，所以我假設是大O，但至于時間復雜性--很難說。有什么想法或指導嗎？謝謝！
myarr = [1,2,3]
k = 2 ]
finalarr = []
def subsets（n, k）。
if k == len（n）。
if not n in finalarr:
finalarr.append(n)
回傳
for i in n:
aux = n[:]
aux.remove(i)
結果 = subsets(aux, k)
if not result in finalarr and result:
finalarr.append( 結果)
subsets(myarr, k)
print (finalarr)
uj5u.com熱心網友回復：
尋找一個給定長度（k）的陣列的所有子集的最佳時間復雜度等于k的2次方。解釋是考慮陣列的每個元素在兩個可能的狀態：屬于或不屬于一個子集。棘手的是要記住空集的問題。這里有一個例子。
這也可以通過繪制函式subsets的呼叫樹來驗證：第一層由一個呼叫組成，下一層由n呼叫組成，然后是n-1呼叫，依此類推，直到最后一層有n-k 1呼叫。由于函式subset中的運算元（除遞回呼叫外）是恒定的，我們可以簡單地將每一級的呼叫數相乘，得到上述的表達。
有兩點要注意：
這不是最有效的演算法，因為每個子集都要產生幾次。例如，
(1)的子集(1, 2, 3)可以通過首先消除2然后消除3來產生，或者反過來。代碼包含以下條件：
if not result in finalarr and result: finalarr.append( result)這個條件永遠不會被滿足，因為函式
subset總是回傳None。因此，這幾行代碼是多余的。
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/330534.html
標籤：