遞歸算法的空間複雜度

我在採訪時被問到解決檢查pallindrome問題的有效方法。遞歸算法的空間複雜度

現在我可以做兩兩件事：

從i開始= 0到i = N/2和比較第i和n i個字符爲相等。
我可以使用遞歸來檢查第一個和最後一個是否相同，而其餘的字符串是pallindrome。

第二個是遞歸的。我的問題是算法的遞歸和非遞歸版本的空間複雜度有什麼區別？

來源

2012-05-30 dharam

在

有一個讀基本上，因爲你存儲在執行堆棧的遞歸調用遞歸算法會增加開銷。

但是，如果遞歸函數是調用的最後一行（尾遞歸），那麼沒有額外的懲罰。

那當然兩種算法都是一樣的。

來源

2012-05-30 17:22:42 Yannis

理論上它們具有相同的空間複雜度;它在很大程度上取決於tail recursion是否可以優化。

如果是這樣，堆棧會在每次遞歸時被替換，所以不會受到懲罰。

來源

2012-05-30 17:20:37

對於大型數據集，即使使用尾遞歸，也會導致StackOverflow錯誤。沒有？ – Sudhakar

@Sudhakar這正是尾遞歸優化防止:) –

這個程序是一個有效的尾遞歸的例子。這產生了計算器。請糾正我，如果我錯了。

 public class TailTest { \t public static void main(String[] args) { \t \t System.out.println(TailTest.iterate(100000)); \t } \t \t public static long iterate(int n){ \t \t if(n==1) return 1; \t \t \t \t return iterate(n-1); \t } }

– Sudhakar

遞歸算法的空間複雜度

回答

相關問題