動機
以 n 除以 b 寫出的遞歸式,往往掩蓋了輸入大小是整數這個事實。把上取整換成精確分數,可能改變遞歸停止的位置,尤其是在最小的輸入處。證明應從實際反覆取整後的大小出發,並且既要計入內部工作,也要計入最後的葉子。
三種常見的增長情形來自各層之上的幾何級數求和。當代價項含有對數時,等號情形會更微妙:多出一個對數因子並不總是正確答案,而倒數對數會產生另一個邊界。
下面的整數大小分析處理的是各分支一致、固定分支數的遞歸,並明確要求基礎值與代價項的界為正。分支不等、任意依賴數據的分支,以及負代價之間的抵銷,都不是這些假設的推論。
定義
定義 3.2.1
(一致的取整遞歸及其代價項)
固定整數 、 和實數指數 。設正的基礎值為 。對整數 ,考慮
其中 c、C 是固定的正常數。這 a 次遞歸調用的輸入大小都是上式所示的取整後大小。這是一個數學意義上的工作量遞歸;常數和界與 n 無關。
記 。上取整遞歸在大小為一時停止,因此大小為一的調用是基礎情形,而不是又一次遞歸調用。空輸入的工作量可以另行定義,且從不進入這個正大小的遞歸。
定義 3.2.2
(下取整版本及其基礎情形約定)
對於下取整版本,對每個滿足 的整數 n 取固定的正有界基礎值,並且僅對 應用 。此時 c 與 C 約束的是該遞歸範圍內的代價項。這一基礎情形約定避免了出現未定義的大小為零的調用。
所有漸近常數可以依賴於 a、b、d、c、C 以及有限個基礎值,但不依賴於 n。算術運算代價與位元運算代價的區別必須已經計入 g 之中;遞歸式本身並不聲明長整數算術是常數代價。
定理/命題
定理 3.2.3
(上取整遞歸:三種幾何情形)
對於上取整遞歸,
遞歸恰有 層內部展開,以及 個葉子。這些公式也涵蓋鏈狀情形,即 a 等於一且 d 為零,此時工作量是對數級而非常數級。
定理 3.2.4
(下取整遞歸具有相同的增長階)
在所述的下取整基礎情形約定和正的代價項界之下,同樣的三種漸近情形成立。對至少為一的 n,其深度為 ,並且每個葉子的大小從一到 b 減一。
不需要對某個未指明的未知工作量函數假設單調性:每一層上實際取整後的子問題大小可以被直接估計。
定理 3.2.5
(臨界對數代價項還有三個閾值)
在恰為冪的輸入 上,改為假設 ,使用同樣的正基礎值,並且
在遞歸的冪輸入處成立,其中 r 為實數。那麼當 L 趨於無窮時,
基礎情形和有限個較小的冪另行處理,因此不會對零取對數。該命題僅限於恰為冪的輸入;其證明並不會不加說明地變成一個取整後分支混雜的定理。
證明思路或證明
求出每一層取整後的大小
證明
(取整後的大小與逐層求和)
對正整數 b 和實數 x,反覆相除滿足
整數 j 不小於左邊的式子,當且僅當 ,也就等價於 ,由此證明該恆等式。歸納可知第 j 層的大小為 。
第一個大小為一的層滿足 ,從而 。在該層之前,比值大於一,所以
該層恰有 個節點,因為每個內部節點都發出 a 次調用,且大小都相同。它們合起來的代價項,其上下界是 的固定正倍數。這些不等式在 d 為零時仍然有效。
因此,把遞歸展開到實際的葉子,得到
兩邊都包含正的基礎代價。當 n 為一時,求和為空,葉子項就是基礎值;此處無需分配任何內部代價項。
計算求和並保留葉子
證明
(幾何情形與葉子)
令 。若 q 小於一,則其幾何級數的部分和有一致的上界,並且在 n 大於一時至少為一。另外 ,並且因為 L 與 相差不到一,所以 。因此,根節點大小的代價項決定了答案。
若 q 等於一,則每個內部層的貢獻都是 階。這樣的層有 L 個,而葉子的貢獻是 階。總和為 ,得到所述的邊界形式。當 a 為一且 d 為零時,每層只有一個節點,各自帶有正的常數代價,所以對數是必不可少的。
若 q 大於一,則幾何級數的和對正的 L 是 階。其代價項的貢獻為 階,而葉子項恰好是同一階。因此葉子大小的增長佔主導。在這個情形下,葉子並不是低階的修正項,而與內部各層同階。
證明透視
競爭發生在分支與縮小之間,而不只是根節點的代價項
在每一層,分支使節點數乘以 a,而大小縮小使每個多項式代價項除以 b 的 d 次方。它們的比值決定了相繼各層是縮小、保持相當還是增長。正的基礎代價使最後一層始終可見,即使後來對數型代價項迅速衰減也是如此。
下取整的大小同樣允許直接比較
證明
(下取整的大小與同樣的比較)
下取整對應的恆等式是 ,因為在整數除法下,定義下取整的整數區間具有相同的商端點。於是 。
第一個基礎層的大小小於 b 且至少為一,從而 。在每個內部層,,所以
下界的比較來自:當 x 至少為二時,x 減一不小於 x 除以二。因此每一層的代價項都與之前一樣有固定倍數的比較。有限個正的基礎值有正的最小值與有限的最大值,所以全部葉子合起來的代價仍是 階。再次使用幾何級數的各種情形,就證明了下取整定理,而無需借助未經證明的單調性假設去比較 T 在不同輸入處的值。
上界遞推不自動給出雙向運行時間估計
正的局部工作下界才保證各個 結論的下界。程序若只給出局部工作上界,展開樹只能證明上界,不能創造實際不存在的工作。例如單個向上取整減半調用,局部工作為一時總量為對數級,局部工作為輸入大小時總量為線性級;兩種局部工作都滿足同一個線性上界。
實際子調用數也須核實。乘法程序發現零操作數後可能省略某個分支;三分支完整樹仍給出上界,但匹配的下界需要一族不會觸發捷徑的輸入。分別最大化局部工作和各個孩子,也不保證同一輸入能同時達到所有最大值。
所以應先說明遞推是精確工作恆等式、最壞情形上界,還是具有可實現下界的雙向模型。本篇定理針對已聲明的正恆等式;工作更少的程序可繼承上界,卻須另證下界才能聲稱 。優化某些執行不會與完整樹上界矛盾。
臨界對數化為深度上的冪和
證明
(臨界對數化為冪和)
對於恰為 的 n,第 j 層的子問題大小為 。在臨界情形 下,該層合起來的代價項為
階。固定 b 與固定 r 使對數底的因子成為常數。令 h 等於 L 減 j 並求和:
當 r 大於負一時,由初等的積分比較,或者由二進分塊再加上和式的後一半,得到 階。這包括該範圍內的負 r:後一半中的每一項都與 相差一個固定因子,由此得到下界;對遞減冪函數積分則得到上界。對非負的 r,使用相應的遞增函數比較。
當 r 為負一時,和式是調和級數,介乎 與 之間。當 r 小於負一時,該正項級數以一加上其收斂的廣義積分為上界,並以其首項為下界。於是保留下來的葉子項具有同樣的歸一化常數階。代入 L 與 log n 成比例,就證明了全部三個閾值。
這些積分比較針對的是正的純量級數;它們並不假設原來未知的 T 是單調的。這一區分使得精確的整數遞歸在前面各定理中始終保持明確。
例題詳解
例題 3.2.6
(上取整的邊界會改變精確答案,卻不改變其階)
取 以及 。當 n 為八時,深度為三,有八個葉子和七個內部節點,所以 T 為十五。當 n 為九時,深度為四,有十六個葉子和十五個內部節點,所以 T 為三十一。
該遞歸處於葉子佔主導的情形,其中 p 為一而 d 為零,因此兩個答案都符合線性的漸近增長。如果用精確的一半來代替取整後的大小,就會錯過這一精確的跳變及其正確的停止層。
例題 3.2.7
(根佔主導的遞歸仍可能有若干完整的層)
設 且 。當 n 為七時,第一個子大小為三,其子大小為一。總工作量是根的代價項七,加上下一層的代價項 ,再加上四個單位葉子,共十七。
這裏 ,所以總的階是線性的。根佔主導描述的是求和後的量級,並不是斷言所有非根的工作量字面上都消失。
例題 3.2.8
(一個臨界對數會在總量中產生兩個對數)
在 2 的冪上,取基礎值為一,並令 。把各層之和除以 n,得到一加上整數一到 L 的和。當 n 為八時,L 為三,T 為 。
定理給出 。若代價項改為 n,則歸一化的和將是一加 L。代價項中的對數改變了每一層的貢獻,在套用臨界情形之前必須把它計入。
概念視角分析
遞歸樹是以尺度為指標的求和
精確的取整確定了哪些尺度真正出現。多項式代價項在這些尺度之間形成幾何級數,而臨界對數代價項則對剩餘深度形成冪和。證明是一個受控的有限和,並單獨計入邊界,而不是把分數輸入大小代入一個未定義的函數。
常見錯誤
反例模式
上取整遞歸需要正大小的基礎情形
如果只把大小為零聲明為基礎情形,並對每個正的 n 都遞歸地使用 ,那麼大小為一的調用會調用自身。其方程為 ,沒有有限的非負工作量解。在應用任何主定理估計之前,必須先指明取整與終止的假設。
常見錯誤
(只計內部節點的代價項)
只把內部節點的代價項加起來就停下,會漏掉葉子,而每個葉子都要付出一個基礎值。取 與 ,並令 。內部代價項合共 ,但 ;當 時是 ,而不是 。應像上面的逐層求和那樣,明確計入 個葉子。
常見錯誤
(對數型代價項仍沿用邊界形式)
在臨界情形 而代價項含有對數時,容易誤以為仍是 的形式,或只需多乘一個對數。在 2 的冪上取 與 。逐層求和給出 ,所以 無界: 時為 , 時為 。正確的階是 ,這正是 時的臨界對數定理。
不要在沒有證明單調性的情況下使用單調性夾逼,也不要把恰為冪的對數定理轉用到任意不等分的子問題上。負的開銷抵銷、依賴數據的分支以及大整數算術,都需要各自的模型和界。
總結
反覆的整數除法給出精確的上取整、下取整大小以及停止深度。逐層比較把多項式代價項化為帶有正葉子項的幾何級數,而臨界對數則化為深度上的冪和。這就在不隱藏取整、基礎情形或代價模型的前提下,證明了精確的漸近情形。
練習
快速檢查
(對 (基礎值為大小一時取正)進行分類。說明為甚麼除非代價項本來就是按位元度量的,否則該定理本身並不能確定某個實作的位元運算代價。)
比較三與二的一次方。
解答 · 分支產生乘法指數
這裏 p 為 ,並且 ,所以界為 。這是關於所聲明的工作量函數的結論。如果 g 計的是長整數上的字操作,仍然需要另行做位元代價分析;遞歸定理不會把這些操作變成單位位元工作量。
快速檢查
(在 2 的冪上,求一個有兩次半大小調用、代價項為 的遞歸的階。在大小為一處保持正的基礎值。)
歸一化的深度和是調和級數。
解答 · 倒數對數給出 log-log 因子
當 n 等於 時,每一層的貢獻是 n 除以其剩餘深度,至多差一個固定的對數底因子。因此當 L 趨於無窮時,T 除以 n 的階為 。結果是 ,有限個最小的冪以及正的基礎值另行處理。
快速檢查
(對 、 的下取整遞歸,大小一與二處的基礎值均為一,代價項為 ,精確計算 。)
第一個取整後的子大小已經是基礎大小。
解答 · 一次展開得到十
下取整除法把八變為二。因此 。深度公式給出 ,與之一致。若使用上取整,則八會變為三並需再展開一次,得到另一個不同的精確遞歸,儘管對應的大輸入階仍是線性的。