遞推關係描述的是某個特定算法在某個特定成本模型下的表現;它並非單憑「程式是遞歸的」這一事實便可確定。在這裏,陣列索引、固定位寬算術和比較各自花費常數時間。我們計算在給定輸入上的工作量;當輸入值會改變控制流程時,則採用最壞情況的上界。
定義 2.4.1
(某成本模型下的遞推關係)
在指定成本模型下,某算法的遞推關係是一條等式,它把大小為 的輸入上的成本 ,表示為該次調用自身所做的工作(不含遞歸調用),加上它所作遞歸調用的成本。它由程式碼推導而來,並且特定於該模型。
一個遞歸分支,然後一個迴圈
考慮正整數 n 的 F(n):
F(n):
if n <= 1: return
for i = 1 to n: do one unit of work
F(floor(n/2))
定理 2.4.2
(折半遞歸的工作量與堆疊)
設 先執行 次迭代的迴圈,再對 調用自身,且 時立即返回。當 時,其總工作量滿足 ,所以 ,而調用堆疊至多有 個框架。迴圈在遞歸調用之後執行時,結論相同。
證明
(不同迴圈長度構成的等比級數)
當 n 為二的冪時,各迴圈長度為 n, n/2, n/4, ..., 2。它們的總和小於 2n,而單是第一個迴圈已花費 n,所以 T(n)=Theta(n)。調用次數是 Theta(log n),但每次調用所做的工作各不相同。把 n 乘以調用次數,等於把每個迴圈都當作最大的那個來計算。
這個論證並不依賴 n 是二的冪:重複取下整只會令迴圈長度減少,所以它們的總和至多為 2n;而對於 n>1,第一個迴圈仍然給出線性的下界。調用堆疊有 Theta(log n) 個框架;時間上界並不會令空間上界變成線性。
反例模式
迴圈長度乘以調用次數會高估
一個誘人的界是把最大迴圈長度乘以調用次數,從而斷言 。當 時,各迴圈的長度是 ,所以確切總數是 ; 共調用 11 次,其中 10 次執行迴圈。乘積 約高估 5 倍。對 ,確切總數是 ,所以 , 的斷言不成立。正確的算法是把不同的迴圈長度相加,這是一個等比級數。
例題 2.4.3
(精確計算 F 在 n = 16、10 和 1 時的工作量)
當 時,各迴圈長度為 ,而 立即返回:總數為 ,共調用 5 次。當 時,參數依次為 :迴圈合共 ,介於 與 之間,共調用 4 次。當 時函數立即返回,工作量為 ,只有一次調用;不等式 只對 陳述。
概念視角組合
二進位數字給出精確成本
迴圈長度是 ,即把 的最後 個二進位數字去掉。價值 的數字,在 時對 貢獻 ,因此對 的總和貢獻 。逐位相加得 ,其中 是 的二進位展開中 的個數。參數為 的調用不執行迴圈,所以 時 。對 這是 ,對 是 ,對 是 。
兩個分支不一定代表二次時間
對長度為 n 的陣列進行合併排序,會對兩半各作一次調用,然後以線性工作量把已排序的兩半合併到一個輔助陣列中。當 n=2^k 時,其遞推關係為
其中 c,d>0 代表理想化實作中的常數成本。在深度 j,共有 2^j 個大小為 n/2^j 的子問題;它們的合併工作總量為 cn。內部層共有 log_2 n 層,另加 n 個常數成本的葉節點。因此在此模型下 T(n)=cn log_2 n+dn=Theta(n log n)。對於任意 n,分成下整和上整兩半仍保持相同的漸近界。實際的合併在不同輸入上可能進行不同次數的比較,但一個複製所有元素的常規合併,在每個內部節點仍然做線性的工作。
定理 2.4.4
(合併排序遞推關係的封閉形式)
對 , 與 的解是 。因此對常數 ,有 。
證明
(對 k 歸納)
當 時,公式給出 。設公式對 成立。則 。由於 ,這等於 ,即對 的公式。
對任意 (兩半取下整與上整),同樣的漸近界仍然成立;本節不證明這種情形。
例題 2.4.5
(c = d = 1、n = 8 時的合併排序遞推關係)
取 :,,,。公式給出 。按層計算:三層合併各花費 ,共 ;8 個葉節點各花費 ,共 。在 時同樣檢驗得 ,在 時得 。
遞歸調用的次數與每次調用的工作量都必須計算在內。2T(n/2) 表示兩個子節點的成本是相加,而不是相乘。+cn 是遞歸調用以外的工作,在每個節點只計一次。
重疊子問題:一棵不同的樹
定義 W(0)=0、W(1)=1,並對 n>=2 定義 W(n)=W(n-1)+W(n-2)。直接的遞歸實作會獨立地計算這兩項。例如,計算 W(5) 會調用 W(4) 和 W(3),而 W(4) 本身又會再次調用 W(3)。除非程式明確儲存結果,否則參數值相同的調用仍是各自獨立的調用。
設 C(n) 為調用次數(包括最初的調用)。則 C(0)=C(1)=1,且
由於每個非基本情況的調用恰好產生兩個子節點,這棵調用樹是滿的。它有 W(n+1) 個葉節點,因此 C(n)=2W(n+1)-1。葉節點的公式可由相同的遞推關係和基本情況以歸納法得出。因此樸素算法會作出指數級數量的調用:對 n>=2,有 C(n)>=2C(n-2),而 C(n)<=2C(n-1)+1 則給出指數級的上界。這些不等式已足以證明指數增長,毋須求出確切的封閉形式。
定理 2.4.6
(樸素斐波那契(Fibonacci)遞歸的調用次數)
設 為調用次數,,且 時 。則對每個 ,,且 ,所以調用次數呈指數增長。
證明
(兩個歸納證明)
關於公式:,。若對 與 成立,則 。關於下界:由於 不遞減,。又 ,由歸納得 。
證明透視
兩個歸納如何使用遞推式
公式需要兩個基底情形,因為 同時依賴 和 ;先驗證 與 ,歸納步驟才能由 開始。遞推式中的 與公式中的 互相抵消:。下界的關鍵一步,是把 與 比較,而不去解遞推式。這需要 ,而它成立,是因為每個 使 。這個比較捨棄了一部分增長,所以只得出 ,是有效但較弱的下界。歸納每次前進兩步,而 同時為兩種奇偶性提供起點。
例題 2.4.7
(n = 5 與 n = 6 的調用次數,以及最小的情形)
由遞推關係得出,對 n=0,...,5 的調用次數為 1, 1, 3, 5, 9, 15。由下而上的方法則先設定兩個基本值,然後依次計算 W(2)=1、W(3)=2、W(4)=3、W(5)=5。對 n>=2,它進行 n-1 次加法;若之後毋須重構,則只需保留前兩個值。在單位成本模型下,這是 Theta(n) 時間及 Theta(1) 個儲存值。確切的整數會隨 n 增長,所以任意精度下的位元運算成本及以位元計的儲存量,會比這個簡化的計算為大。
當 :,因為 ;由下而上需要 次加法。當 或 時只有一次調用,遞歸立即停止,由下而上不需任何加法。
記憶化是一種由上而下的替代方法:儲存每個已計算的 W(k),並在其後的請求中傳回已儲存的值。需要一個獨立的標記來區分「尚未計算」與一個已計算而值為零的結果。每個參數 0,...,n 至多計算一次,得出 O(n) 次單位成本運算及 O(n) 的儲存量(包括遞歸堆疊和表格)。
常見錯誤
(把堆疊深度當作時間)
仍在執行的框架數是遞歸的深度,不是工作量。 至多約有 個框架,卻需要 時間。把兩者混淆,會得出 的時間,或 的堆疊空間。
常見錯誤
(把相同參數當作同一次調用)
在樸素遞歸中, 在 之下被調用一次,在 之下又被調用一次。除非儲存結果,否則每次出現都是獨立的調用,所以 共作 次調用,而不是 這 6 個不同參數。只數不同參數描述的是記憶化,而不是樸素程式。
已解練習:要推導,不要猜測
快速檢查
(對正整數 n,以下程式遞歸地把 n 減半,並在返回後執行一個 n 次迭代的迴圈。它的時間上界及輔助堆疊上界是甚麼?)
G(n):
if n <= 1: return
G(floor(n/2))
for i = 1 to n: do one unit of work
把迴圈大小與 的比較一下。
解答 · 答案
遞歸調用與迴圈的次序改變了,但迴圈大小仍然是 n, floor(n/2), floor(n/4), ...。它們的總和是 Theta(n)。在最大深度時有 Theta(log n) 個仍在執行的調用,所以堆疊使用 Theta(log n) 個框架。次序會影響工作在何時進行,對於帶狀態的程式亦可能影響輸出,但在所述假設下,它不會改變這個運算次數。
快速檢查
(樸素遞歸計算 要作多少次調用?)
用 及 以內的已知數值。
解答 · 答案
,與 一致。
快速檢查
(某函數對 作一次遞歸調用,其餘只做常數工作。它的時間與堆疊上界是甚麼?)
先寫出遞推關係。
解答 · 答案
遞推關係是 ,基本情形為常數,所以 。遞歸深度為 ,所以堆疊使用 個框架,與折半函數 不同。