帶有記憶功能的遞回河內塔的空間復雜度是多少？
我猜遞回演算法有 2^(n-1) 個遞回呼叫，所以空間復雜度是 2^(n-1)？
閱讀下面的一些評論后進行編輯：我認為這里沒有重復的遞回呼叫，因此記憶根本沒有幫助。如果我使用記憶化，所有遞回呼叫都將被存盤，從而將空間復雜度提高到最大值：2^(n-1)。對于這種遞回演算法，最好不要使用記憶化嗎？
你能證實我的理由嗎？
河內塔問題：串列移動使用“中間”掛鉤將 n 個磁盤從“源”掛鉤移動到“目標”掛鉤。
遞回演算法：
def hanoi_tower_solution(n, source, mid, target):
if n == 1:
disk_move(source, target)
else:
hanoi_tower_solution(n-1, source, target, mid)
disk_move(source, target)
hanoi_tower_solution(n-1, mid, source, target)
uj5u.com熱心網友回復：
我猜遞回演算法有 2 ???1遞回呼叫，所以空間復雜度是 2 ???1？
不是。雖然有那么多的呼叫，但在下一次遞回呼叫之前有呼叫回傳，因此前一次呼叫使用的（堆疊）記憶體首先被釋放，然后再次重用。
重要的是遞回的最深深度。由于 ???1 作為引數傳遞，并且當 ?? 等于 1 時，到達遞回的最深點，深度為 ??。因此空間復雜度為O(??)。
如果我使用記憶化，所有遞回呼叫都將被存盤，從而將空間復雜度提高到最大值：2 ???1。
真的。
對于這種遞回演算法，最好不要使用記憶化嗎？
這取決于具體記憶的內容。如果使用塔的簡單狀態作為關鍵，那么它是無用的，因為在一個解決方案中沒有狀態出現兩次。
我們可以想象一種記憶，其中塔的順序不在鍵中表示，只有一個堆疊上的連續最小圓盤的數量用作鍵——這個子堆疊必須移動到另一個位置. 然后，將 3 個最小的圓盤從塔 B 移動到 C 的移動可以利用記憶解決方案將它們從塔 A 移動到 B。然后您將注意移動的編碼方式，以便它們正確地轉換為實際情況的塔。這將需要大約 O(??) 個條目進行記憶，但是每個條目都會列出要進行的移動，這在要移動的圓盤數量方面再次呈指數級...
記憶化確實沒有太大的好處，因為：
- 無論如何，必須進行所有 2 次???1移動，因此沒有時間增益。
- 有一個不需要遞回的簡單解決方案：光碟的數量、當前狀態和移動編號唯一地定義了必須播放的移動。Wikipedia上解釋了該邏輯。然后它以恒定的輔助空間復雜度運行（因此不計算用于表示當前狀態的記憶體）。
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/365905.html
下一篇：遞回數字和