本課程之後的每個斷言,例如「堆的插入需要對數時間」或「並查集近乎常數」,都是關於成本如何隨輸入規模增長的陳述。只有說明了計算甚麼、輸入規模是甚麼、考慮哪些輸入,以及符號 、、 的確切含義,這樣的陳述才有意義。本單元提供這些基礎。它不涉及任何數據結構;之後關於動態陣列、堆與排序的單元都依賴它。
成本模型
碼錶只能量度某一部機器、某一個編譯器和某一個輸入。要研究算法本身,我們計算抽象的操作次數。
定義 19.1.1
(單位成本 RAM 模型、輸入規模、成本函數)
在單位成本 RAM 模型中,下列每項花費一步:對固定寬度字作算術運算或比較、讀寫一個陣列儲存格或變量、一次跳轉。輸入規模 是指明的參數:陣列元素個數、頂點數與邊數,或某個數的位元數。對算法 與輸入 ,令 為步數。最壞情形成本為
最佳情形成本取最小值,平均情形成本則在規模為 的輸入上按指明的概率分佈取期望。
有幾種變體值得留意。在比較模型中只計算鍵值比較,如排序下界所用的那樣。在位元成本模型中,對 位元的數作算術約花費 步,當數不受字長限制時這很重要。若數不斷增大,單位成本假設會產生誤導:把一個整數反覆平方,每次長度加倍,把每次平方當作一步便低估了工作量。因此,成本斷言必定相對於某個模型,輸入規模也必須按該模型度量。對以二進位給出的整數 ,輸入規模是 個位元,所以迴圈執行 次的算法,相對輸入規模是指數級的。
記號
定義 19.1.2
(、 與 )
設 。若存在常數 與 ,使得對所有 都有 ,記作 。若存在 與 ,使得對所有 都有 ,記作 。若兩者皆成立,即 且 ,記作 。
常數可以依賴 與 ,但不能依賴 。此記號只描述 很大時的行為:門檻 捨棄了有限個小輸入。等號只是慣例; 代表被 的常數倍從上方界住的函數集合,「」表示 屬於該集合。 只給出上界:線性算法同時是 ,這是正確但沒有資訊量的。 則表示增長階恰好與 相同。
命題 19.1.3
(增長率的運算規則)
設 。
- 常數與低次項。若 ,係數為實數且 ,則存在 與 ,使對所有 有 ;即 。
- 和。若 且 ,則 。
- 積。若 且 ,則 。
- 遞移性。若 且 ,則 。
證明
(吸收低次項與常數相乘)
(1) 若 ,正常數 取 即可;故設 ,並令 。當 時,每個 的 至多為 ,所以 。上界: 時 。下界:。若 ,則 ,故 。取 、、 即可。
(2) 對兩個假設分別取 與 。當 時, 。
(3) 對同一範圍的 ,所有量都非負,所以兩個不等式可以相乘:。
(4) 若 時 ,且 時 ,則 時 。
證明透視
多項式的門檻從何而來
只有 (1) 的下界用到 ;上界只需 。關鍵一步是把所有低次項歸併成單一的 ,使它與首項的比較化為關於 的一個不等式 。門檻 就是首項開始至少佔優一倍的位置,而且它依賴係數,並非只依賴 。以 為例:、、,而 恰好在 時成立( 時 )。此處不可能取 之類的門檻,因為 。若 ,則對任何 下界都不成立,因為 最終為負。
對數方面,,所以各底數只差一個常數倍,在 與 中省略底數。
增長層級
當 很大時,常見的階按下列次序遞增:
其中 表示 但 。兩個比較可說明證明方法。第一,:由於 時 ,有 。第二,對任何固定的 , 都不是 。令 ,則 ,其極限為 ,所以當 足夠大時,每一步至多把 乘以 ,故 。因此 無界。層級中其餘比較,我們當作標準事實使用。
命題 19.1.4
( 的極限判別法)
若 且 ,則 。
證明
(夾住比值)
在極限的定義中取 。最終 介乎 與 之間,所以對所有足夠大的 有 ,這給出 所需的兩個界。
概念視角分析
用上極限與下極限描述記號
當 足夠大時若 ,常數可以換成兩個極限量: 恰好當 ; 恰好當 。對 與 ,比值在 與 之間交替,故 、:雖然普通極限不存在,仍有 。
計算程式碼的步數
計算最內層語句的執行次數,然後化簡。巢狀迴圈中,若內層次數不依賴外層索引則相乘,否則求和。控制變量每次加倍的迴圈約執行 次。
例題
例題 19.1.5
(帶明確常數的二次多項式)
證明 。下界:對所有 有 ,所以 、 可用。上界:當 時 且 ,故 ,所以 、 可用。因此 。在 檢驗:,且 。
例題 19.1.6
(計算迴圈次數)
考慮 for i in range(n): for j in range(i): work()。迴圈體在 時執行 次, 時 1 次,一般地 次,總共 次。 時為 10。由於 ,且 時 ,所以次數是 。
再考慮 i = 1; while i < n: i = 2*i。 的取值為 ,一旦 迴圈便停止。 時,被測試且小於 10 的值為 ,共 4 次迭代 。 時,值 給出 3 次迭代 。一般地,當 時迭代 次;當 時這是 。
例題 19.1.7
(沒有極限的 )
設 。 為偶數時 , 為奇數時 ;例如 、。因此對所有 有 ,所以 ,取 、、。比值 在 與 之間交替,沒有極限,所以極限判別法不適用,但定義依然適用。極限判別法是充分條件,並非必要條件。
細節與常見錯誤
反例模式
指數中的常數
嗎?不。,而 無界,所以不存在常數 使 對所有足夠大的 成立。相反,。指數中的常數會改變增長類別;乘上常數因子則不會。
常見錯誤
(把等號當成對稱關係)
由 不能寫成 ;由 與 也不能推出 。這個等號表示屬於: 屬於集合 。事實上 是錯的,因為 無界。
常見錯誤
(混淆最壞情形與 O)
「最壞情形」與「」是獨立的概念: 界住一個函數,最壞情形則選出是哪一個函數。可以用 描述最佳情形成本,也可以用 描述最壞情形成本。
以增長率比較算法時忽略了常數:當 時 大於 ,所以二次算法在小輸入上可能更快。漸進分析預測的是縮放行為,例如 加倍時時間如何變化,而不是某個特定 的執行時間。
習題與解答
快速檢查
(1. 證明 是 。)
解答 · 解答 1
當 時 ,所以 。於是對所有 有 。因此 、、 證明 。
快速檢查
(2. 計算內層語句執行次數:對 :令 ;當 時令 。求 時的次數,並給出增長類別。)
解答 · 解答 2
對給定的 , 的取值為 ,其中 ,所以迴圈體執行 次。 時, 的次數為 ,總和為 。一般地,總數至多為 。至少有 個索引滿足 ,每個至少貢獻 ,所以總數至少為 。兩個界都是 階,所以總數為 。
快速檢查
(3. 判斷真假並說明理由:(a) ;(b) ;(c) ;(d) ;(e) 。)
解答 · 解答 3
(a) 真:。(b) 假:比值為 ,無界。(c) 真: 時 。(d) 假: 無界。(e) 真:,是 的常數倍。
快速檢查
(4. 的算法在 時用 8 ms。預測 時的時間。若改為假設 ,大約又是多少?)
解答 · 解答 4
對 , 變為三倍,時間乘以 ,得 ms。對 ,比值為 。由於 、,比值約為 ,所以約 ms。預測取決於所假設的增長類別,這就是為何必須論證模型。
快速檢查
(5. 按增長速度排序:、、、、、。然後求最小的 ,使得對所有 都有 。)
解答 · 解答 5
遞增次序:。至於門檻:、、、,所以 在 時不成立,在 時成立。此後一直成立:若 且 ,則 ,因為 時 。所以 。