為什么二叉樹遍歷（如前序）的時間復雜度不是指數級的？例如，在 Fibonacci 數列的常見實作中，它是指數的，因為對于每個實體，您呼叫 Fibonacci 函式兩次。那么，為什么前序遍歷是 O(n)（遞回函式也被呼叫兩次）[我知道它是 O(n)，因為每個節點都被遍歷，所以請不要回答為什么它是在）。與斐波那契遞回實作進行比較回答，因為我想看到不同之處]。
uj5u.com熱心網友回復：
我假設您指的是這個遞回斐波那契演算法，它以數字 ?? 作為輸入，并回傳斐波那契數列中的第??數字：
def fibonacci(number):
if number < 2:
return number
else:
return fibonacci(number - 1) fibonacci(number - 2)
如果我們將每個不同的值number（用于呼叫此函式）視為一個“節點”，那么請注意與二叉樹遍歷問題的一個重要區別：
這個斐波那契演算法將多次訪問同一個節點，并且隨著對已經訪問過的“節點”進行遞回呼叫，情況會變得更糟。遞回樹并不是真正的樹，而是有向無環圖。這是呼叫時的遞回樹Fibonacci(5)：
所以我們看到Fibonacci(3)計算了兩次，每次都做更深層次遞回的全部作業。所以Fibonacci(2)和Fibonacci(0)分別被稱為 3 次和Fibonacci(1)5 次。總共有 15 次“訪問”，包括重復。
遞回樹遍歷演算法不會發生這種情況，遞回樹實際上是一棵樹（相當于被遍歷的樹）。
這解釋了時間復雜度的差異。
它還解釋了為什么可以通過避免重復的“節點訪問”來改進這種樸素的斐波那契演算法，使其也變成 O(n)。
uj5u.com熱心網友回復：
有兩種查看方式：
- 對于每個節點，您將進行兩次遞回呼叫。這已經告訴您，對于每個附加節點，它都是一個常數因子，無論該節點位于樹中的哪個位置。
但以防萬一這對你來說還不夠，還有另一個觀點：
- 在每次遞回呼叫中，子問題減半。因此，您將呼叫量加倍，但將要完成的作業量減半。
這兩種情況都不同于“有缺陷的斐波那契實作”，因為您永遠不會多次訪問一個節點。在斐波那契示例中，您一遍又一遍地做同樣的作業。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/395969.html
下一篇：按給定范圍對資料進行分組