動機
對冪次代價項所作的精確遞歸樹計算顯示,主導工作量可能來自三種不同的來源。實際算法的代價項往往只知道漸近界,或者帶有對數因子。更一般的定理可以處理這些情形,但其假設不可省略:若代價項出現振盪,則僅僅根代價項很大,並不能阻止某個更小的子問題具有更大的代價項。
我們在除數的冪次上證明一個常見形式。此定理並非適用於子問題大小不相等、或任意帶向下取整與向上取整的遞推式的通用規則。配套的遞歸樹單元另行處理了一個平衡取整的例子。
定義
定義 1.4.1
(冪次上的遞推式)
固定整數 、,並令 。對於 ,,令 ,且
其中 在這些冪次上非負。所有漸近界均指 時的界,其中 以及假設中的常數保持固定。 表示任意一個大於一的固定底數的對數。
定義 1.4.2
(正則性條件)
第三種情形中使用的正則性條件是:存在 ,使得對所有足夠大的 的冪次,
它比較的是一個節點的所有子節點的代價項總和與該節點自身的代價項,而不是僅僅在根處把 與某個冪函數相比較。
定理
定理 1.4.3
(除數冪次上的主定理)
在上述定義下:
- 若對某個 有 ,則 。
- 若對某個固定的 有 ,則 。
- 若對某個 有 ,且正則性條件成立,則 。
定理 1.4.4
(逐層求和恆等式)
對於 ,精確的遞推式給出
證明思路
證明
(逐層求和:恆等式與三種情形)
展開遞推式可知,第 層有 個大小為 的節點,並且共有 個葉子,由此證明該恆等式。由於 ,僅葉子就已給出階為 的正下界。
在情形 1 中,適當放大常數以涵蓋有限多個較小的冪次之後,每一層的代價至多為
對 求和,由於它被一個收斂的幾何級數所控制,故得 。葉子提供了相應的下界。
在情形 2 中,忽略最小大小的有限多層,因為在這些層上漸近不等式未必已經成立。在其餘範圍內,第 層的總代價項介乎 的兩個常數倍之間。對於固定的 ,有 :上界為 ,而後一半的項在相差一個常數的意義下給出匹配的下界。被略去的小規模層與葉子僅貢獻 ,因此 。
在情形 3 中,只要子問題大小高於正則性的閾值,就應用正則性。深度 處的總代價項至多為 ,所以這些層的總和為 。一旦大小降到固定閾值以下,由於只涉及有限多個 的冪次大小,每個節點剩餘子樹的代價被一個常數所界定。這樣的節點至多有 的常數倍個,它們的總代價為 。根代價項給出 ,從而證明了匹配的下界。
證明透視
正則性控制了甚麼
情形 3 的兩個假設分別負責求和中的兩個不同部分。間隙 使葉子的貢獻 相對 可以忽略,答案才可以是 ,而不是兩項之和。正則性控制的是另一部分:它說明每一代合併代價項之和至多是上一代的固定比例 ,所以逐層求和是一個收斂的幾何級數,由首項主導。單靠間隙只是把根代價項與 比較,並不說明之後某一代的代價項會不會超過根,下面的振盪例子正說明這一點。匹配的下界是容易的一步,因為根代價項本身就是求和中的一項。
例題詳解
例題 1.4.5
(較小的代價項)
對於 ,有 ,且 。由情形 1 得 。
例題 1.4.6
(對數代價項)
對於 ,有 且 。由情形 2 得 。這推廣了配套單元中的精確逐層計算。
例題 1.4.7
(滿足正則性的根主導工作量)
對於 ,有 ,且 。正則性條件在 時成立,所以由情形 3 得 。
常見錯誤
反例模式
缺乏正則性的大代價項
取 ,當 為偶數時令 ,當 為奇數時令 。它始終滿足 ,但在 為奇數時,兩個子節點的代價項之和為 ,遠大於根代價項 。因此沿這些冪次, 不是 。可見情形 3 中的正則性條件不能簡單地去掉。
常見錯誤
(把定理套用到取整遞推式)
關於 的冪次的定理,並不會自動證明任意取整遞推式也有相同的界。這需要另行作比較論證或遞歸樹論證。
常見錯誤
(在情形 2 中使用負的對數指數)
情形 2 要求所述的固定 。若代入負指數,需要另作求和論證,下面的調和級數例子正說明這一點。
確定臨界指數
指數 描述葉子的數目:。它是用來與非遞歸代價項相比較的參照尺度,不必是整數。例如,若 且 ,則 。代價項 在多項式意義下小於 ,而 在多項式意義下大於 。比較必須依據實際存在的正指數間隙,而不能僅僅觀察幾個輸入處的數值差異。
漸近記號中隱含的常數對給定的遞推式是固定的。在情形 1 中,必須存在固定的 與常數 ,使得對每個足夠大的允許大小都有 。在情形 3 中,同樣必須存在固定的正間隙,以及嚴格小於一的正則性因子 。若某個因子隨 趨於一,則它不滿足帶單一固定 的正則性條件。
例題 1.4.8
(非整數的臨界指數)
對於二的冪次上的 ,有 。任取固定的 滿足 ,則 ,由情形 1 得 。若把 四捨五入為二,並將二次界當作緊確結果,則是錯誤的。
審視逐層求和
精確展開使證明與任何具名情形相分離。在第 層,因子 計數節點個數,自變量 是每個節點的大小。基礎項是 ,而不是再一次應用 ,除非遞推式明確這樣定義。當 時,和式為空。這些約定避免重複計算葉子。
在代價項匹配的情形中,令 。子問題大小足夠大的某一層的總代價與 成正比。靠近根的層 較大,靠近葉子的層 較小。把所有層相加就得到一個冪和。當 時,每個相關層貢獻階為 ,而層數提供一個對數因子。當 時,各層代價構成等差數列,其和提供兩個對數因子。
條件 使得本定理所用的初等冪和估計一目了然。其他指數可能有不同的行為。例如,對 定義 。它比 小一個對數因子,但對任何固定的 都不是 。逐層恆等式給出 ,即對大的冪次為 。調和和的界可透過與 比較得到。這個例子說明了為甚麼對情形 1 而言,「小於 」並不足夠。
理解正則性
不等式 表示一個節點的各子節點的代價項之和至多是該節點代價項的某個固定比例。反覆應用它,可使各層的總代價項呈幾何遞減,直到子問題大小降到閾值以下。有界的最終子樹貢獻另行處理;正則性不需要在基本大小本身成立。
在振盪反例中,問題不在於負的代價項或古怪的基本情形。每個代價項都為正且至少為 ,但沿著二的奇數冪次,子問題落在偶數指數上,具有大得多的三次代價項。這使得下一層超過根的代價,且倍數無界。僅有 的漸近下界並不比較相鄰的層,因而不能確立根主導。
正則性檢驗應當用實際的函數和實際的自變量來寫出。對於 且 ,計算 。比值是固定的 ,所以 可行。僅僅聲稱 「看起來很大」,遺漏了證明所需的條件。對於含有多項或振盪的函數,比值可能需要更細緻的分析。
漸近界與精確代價
該定理給出漸近上界和下界,而不是精確常數,也不是小輸入時的精確值。直接展開對於檢查實作或某個擬議公式仍然有用。若 ,且在二的冪次上 ,則精確計算給出 。它與情形 3 一致,但僅憑該定理無法確定係數二或低階項。
如果 僅作為算法每次調用的工作量的上界已知,那麼求解上界遞推式本身並不能證明該算法的匹配下界。緊確的 斷言需要對算法本身的適當下界,或者一個工作量非負的精確遞推式。同樣,總工作量的遞推式並不自動界定峰值空間或並行經過時間;遞歸子問題可能以不同方式共享或重疊這些資源。
取整與適用性
許多程式把任意輸入劃分為大小為 和 的子問題。上面的證明假定每個節點的大小都恰為 ,且停止深度一致。取整往往可以控制,但所需的界取決於遞推式與基本情形。帶線性代價項的平衡二路劃分已在遞歸樹單元中另行證明;那一具體論證並不是對每個取整遞推式的證明。
在應用本定理之前,應檢查遞歸調用次數、除數、代價項、固定參數、基本情形和輸入定義域。形如 的遞推式具有不同的形狀。類似地,含有兩個不等大小子問題的遞推式,若無比較證明,也不能硬套進相同的參數。符合定理的假設是求解的一部分,而不是點出某個情形之後可有可無的形式。
完整的情形選擇計算
考慮三的冪次上的 ,基本代價為正常數。首先計算 。對於大的 ,,所以代價項為 。情形 2 適用,取 ,得 。對數底數之間的常數因子不影響結論。其中的項 保證了靠近基本情形處的代價項為正,但漸近分類取決於大的輸入。
再考慮 。同樣 ,但代價項在多項式意義下更大。計算正則性比值:。因此 可行,情形 3 給出 。同時寫出指數比較和比值檢驗,可以避免僅憑一個假設就得出根主導的結論。
這兩個例子還說明,為甚麼相同的分支因子會導致不同的總代價。在第一個例子中,節點的數目恰好抵消了每個節點冪次項的二次下降,使得每一層都留下一個對數代價項。在第二個例子中,每一層的代價是前一層的固定比例。該定理把這些逐層計算打包起來,但並沒有免除識別正確代價項的需要。
對小規模尾部的檢查
在情形 3 中,低於正則性閾值的第一層未必全由葉子構成。其節點在大小降至一之前可能還有若干代。然而閾值是固定的,低於它的 的冪次只有有限多個。因此,對於固定的遞推式,這些大小中最大的完整子樹代價是一個常數。把該常數乘以邊界處的節點個數,便得到所需的 尾部。這明確地計入了基本情形的工作量,同時沒有在未作假設之處應用正則性。
總結
逐層恆等式把遞推式化為代價項之和。多項式意義下較小的代價項由葉子主導,匹配的冪次累積出一個對數和,多項式意義下較大且滿足正則性的代價項由根主導。正則性是一個具有明確用途的假設。
練習
快速檢查
(將該定理應用於 。)
先算 ,再與代價項的指數比較。
解答 · 答案
此處 ,且代價項在多項式意義下更小,所以 。
快速檢查
(將它應用於 。)
先算 ,再判斷代價項屬於哪一種情形。
解答 · 答案
此處 ,,且代價項與 匹配,所以 。
快速檢查
(檢驗 的正則性。)
計算 並與 比較。
解答 · 答案
有 ;正則性在 時成立,結果為 。
快速檢查
(為甚麼葉子給出階為 的下界?)
數一數葉子的個數及每片葉子的代價。
解答 · 答案
共有 個葉子,每個葉子的代價 為正。