遍歷二叉樹迭代或遞歸 - 複雜性分析

我聽過一些意見，二叉搜索樹中的迭代查找比遞歸方式更有效，是這樣嗎？
（我知道在空間方面，迴避更昂貴）遍歷二叉樹迭代或遞歸 - 複雜性分析

來源

2014-03-26 JavaSa

就時間複雜性而言（大O），如果您的算法正確實施，應該沒有任何區別。每次遞歸調用在堆棧上分配新空間時，遞歸通常會在空間上較重。我正在談論你的特定二叉搜索樹結構，但通常這也是正確的。

來源

2014-03-26 18:27:55

這隻有在語言實現沒有實現TCO時纔是正確的。事實上，完全的TCO幾乎肯定是不需要的;對於自我尾巴呼叫的較少侵入性優化，我相信即使在C中也可以廣泛使用，這對於這種應用來說應該是足夠的。 – dfeuer

@ peter.petrov嘿！你能否給我一個二叉樹遞歸遍歷的確切公式。也許有一些鏈接。我GOOGLE了，但無法找到它。其實我想找到我的算法是二叉樹遍歷+其他邏輯的複雜性。我對其他邏輯有複雜性，但對於樹部分我知道的是O（n）。 –

遞歸搜索和迭代搜索之間確實沒有區別，因爲無論如何遍歷樹的高度檢查左節點或右節點而不是兩者（並且這適用於迭代和遞歸），因此你總是遍歷樹的高度。

來源

2014-03-26 18:32:13 ucsunil

理論上沒有變化。對於平衡BST，bigO將是O（n）和O（logn）。遞歸遍歷在紙上看起來很乾淨。但是它有很多開銷。當一個函數被遞歸地調用時，調用函數的狀態必須被存儲在堆棧中，並且控制被傳遞給被調用的函數。但是當你迭代地做時，你不會有這樣的開銷。所以出於實際的目的，你應該使用迭代方法。

如果您編寫遞歸代碼，並且如果事實證明是尾遞歸，大多數現代編譯器都會嘗試通過將其轉換爲迭代代碼來優化它。

來源

2014-03-26 18:39:49 arunmoezhi

@arnumoezhi：那是你說話的開銷，是與程序的運行或只是內存問題的表現掛鉤 – JavaSa

@ peter.petrov：想聽聽你的意見以及 – JavaSa

@JavaSa：兩者。在最壞的情況下，你的堆棧空間是O（n），你只需使用遞歸調用即可獲得性能 – arunmoezhi

很大程度上取決於您的語言實施！如果程序調用在您的語言中是昂貴的，那麼手寫迭代可能會更快。如果過程調用總是推棧，那麼手寫迭代可以節省內存。在像Scheme，Haskell，ML等函數式語言中（我認爲也是基於基於棧的語言，如Postscript或FORTH），您通常可以期望在樹查找操作中找到的「尾遞歸」轉換爲迭代在引擎蓋下，所以沒有區別。事實上，這種特殊形式的尾遞歸（函數返回本身的值）很可能會被甚至不支持完全尾部優化（TCO）的編譯器優化。

來源

2014-03-26 18:45:40 dfeuer

遍歷二叉樹迭代或遞歸 - 複雜性分析

回答

相關問題