我無法推理這是什么時間復雜度。我正在撰寫一個回溯函式來解決問題。為簡化起見，假設我有一個大小為“a”的串列，并且可以將 0 或 1 放入串列的每個元素中。在嘗試了所有組合后，我回來了。這顯然是 2^(nm)。
但是，如果在每次遞回呼叫期間我都有固定數量的作業要做呢？我一直在推理這里的復雜性。你能指出我的來源嗎？在我的本科學習中，我只記得碩士定理，但這種方法無關緊要。（我們減去而不是除以得到子問題）
def myfunc(x,a):
if x == a:
return
myfunc2() #Some constant time work
myfunc(x 1,a)
myfunc(x 1,a)
uj5u.com熱心網友回復：
在您的情況下，時間復雜度為T(n) = m 2T(n - 1). 雖然我們不能在這里應用馬斯特定理，但我們可以使用替換：
T(n) = m 2T(n - 1)
= m 2(m 2T(n - 2))
= m 2m 4(m 2T(n - 3))
= ∑(i = 1, i = n) m2^i
對此進行評估，我們有m2^n或 ?(2^n)。
與可讀性相比，遞回并沒有真正為您提供任何好處。但是，如果您將其與您評估過的內容結合起來，您可能會看到節省。在這種情況下，評估時間復雜度變得更加……復雜。
uj5u.com熱心網友回復：
時間復雜度顯然是指數級的。
除非小于 2 ，myfunc2()否則貢獻可以忽略不計。x
也許如果 myfunc2() 正在搜索 42。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/492022.html