動機
程式在幾個例子上給出合理答案,是證據,卻未證明對所有合法輸入都正確。短程式也未必快。算法分析分開兩個問題:結果是否滿足規格,以及輸入增大時需要多少工作。有效的證明須說明輸入假設、執行過程保持甚麼性質,以及執行為何終止。
陣列從零編號。除非另述,假設隨機存取機模型中,索引運算與元素比較均為常數時間。後面的複雜度斷言依賴這些假設。
定義
定義 1.1.1
(規格與正確性)
前置條件描述合法輸入及初始狀態假設;後置條件描述所需結果。算法若在每次由前置條件開始且終止的執行中,都滿足後置條件,稱為部分正確。若還保證每次這種執行均終止,則為完全正確。迴圈不變量是在第一次迭代前成立,且每次實際執行的迭代都保持的命題。
使用不變量時,先證初始化及保持性,再把它與迴圈條件的否定結合,推出後置條件。不變量不必就是後置條件,因為它須描述工作尚未完成的中間狀態。證明終止可用每次迭代嚴格減少的非負整數,稱為變式(variant)。只說某變量有改變不足夠,它可能無限增大或來回擺動。
定義 1.1.2
(漸近界與輸入大小約定)
對最終非負的函數, 表示存在與 無關的常數 ,使所有 都滿足 。反向的常數倍下界記作 ,兩者均成立記作 。最壞時間是所有大小為 的合法輸入中,成本的最大值;最佳或平均時間是不同斷言,須另行定義。
必須先指定輸入大小。含 個固定大小鍵值的列表,其大小與 成正比;正整數 的二進制表示卻只需 位元。執行 次迭代雖然對數值為線性,未必對位元長度為多項式時間。任意長整數的加法也不能自動視作單位成本。計算模型是定理的一部分,不能在結論之後才補猜。
定理 / 命題
定理 1.1.3
(半開區間的二分搜尋)
設 按非遞減次序排列,目標為 。以下算法在目標存在時返回含 的索引,否則返回 NOT_FOUND。它在 次迭代內終止,使用常數輔助空間。
lo = 0; hi = n
while lo < hi:
mid = lo + floor((hi - lo) / 2)
if A[mid] < t:
lo = mid + 1
else if A[mid] > t:
hi = mid
else:
return mid
return NOT_FOUND
定理 1.1.4
(合併排序)
遞歸地排序兩半,再合併已排序的兩半,所得結果是輸入的已排序排列。若合併以線性次數讀寫元素,則 時最壞時間為 。標準陣列實作除輸入外使用 輔助儲存,另有 遞歸堆疊。
證明思路或證明
證明
(二分搜尋:不變量與終止)
二分搜尋保持 ,以及「若目標在任何地方出現,則它在半開區間 的某索引出現」。最初整個陣列均保留。若 ,有序性排除所有不大於 的索引,更新 後命題仍真。若 ,有序性排除所有不小於 的索引,更新 後仍真。相等時立即返回合法索引。若正常離開迴圈,區間已空,不變量遂保證目標從未出現。
整數長度 在每次沒有返回的迭代中嚴格下降,且保持非負。迴圈執行時 ,每次更新至少移去中點或包含中點的一段;新長度至多為舊長度一半的下整數。因此 時至多有 次迭代, 時沒有迭代。中點公式也避免直接計算 ;固定寬度整數仍須能安全表示容許的索引差。若有重複值,此算法未保證返回第一次出現的位置,那是另一規格。
證明透視
正確性與終止填補不同缺口
二分搜尋不變量指出存在的目標必須留在哪裏,本身卻不保證迴圈停止。遞減區間長度補上此論證。反之,區間縮小只能證明終止,不能證明丟棄位置安全。必須逐一檢查每個分支的保持性與嚴格下降,兩者合起來才完成證明。
證明合併運算
證明
(合併得到有序排列)
設兩個輸入序列 已排序。維持指向各自第一個未使用元素的指標,以及輸出前綴。不變量說明:此前綴已排序,恰好包含已消耗的元素及其重數,而且每個已輸出元素均不大於任何未使用元素。開始時前綴為空。選較小的當前首元素,相等時取左邊,並附加到輸出。各首元素均為自身剩餘部分的最小值,所以選出的元素在全部剩餘元素中最小,保持不變量。當某序列耗盡,把另一序列已排序、且不小於輸出前綴的剩餘部分接上。
每次輸出一個元素,未使用元素數便減一,故必終止。最後結果已排序且完整保留全部輸入元素及重數。單證有序性不足夠:丟棄全部鍵值也會輸出有序序列。相等時先取左邊,還保持兩半中相等鍵的相對次序;若遞歸排序亦穩定,整個算法便穩定。
遞歸正確性與時間式
證明
(合併排序:歸納與遞推式)
對 作強歸納。空陣列及單元素陣列已是自身的有序排列。若 ,兩半均較小,歸納假設保證它們的排序結果正確;合併證明再保證合併結果是原輸入的有序排列。這是迴圈不變量證明的遞歸對應;遞歸調用須有更小參數及基本情形,不能自行證明自己。
當 為二的冪,時間滿足 的常數倍界,基本成本為常數。第 層有 個大小 的子問題,非遞歸總工作與 成正比。共有 個非葉層,葉節點只加線性工作,故得到所述階。一般 使用上下整數兩半,樹深至多 ,每層合併總工作至多線性,得上界。對下界,前 層中,每層的子陣列長度均至少為二、總長度為 ,合併它們至少付出線性的複製成本,所以總和為 。這是對指定合併實作的下界,不是所有排序算法的下界。
空間、遞推式與計數對象
時間式加上兩個遞歸調用的成本,因為兩者均執行。最高同時使用的輔助空間卻不同:兩調用可依次進行,共用一個暫存陣列。長度 的緩衝區已足夠,同時存在的調用記錄只有對數個。把整次執行分配過的空間相加,是總分配量而非最高存活記憶體;兩者未必相同。
寫遞推式前必須解釋各項。分成兩半不自動產生對數時間:二分搜尋只走一支,合併排序卻走兩支。 雖每次處理較小輸入,累加等差數列卻得二次增長。每次合併額外作一次線性複製只改變常數;若合併本身為二次,便改變漸近階。應由算法決定遞推式,不能反過來憑想要的答案挑選遞推式。
概念視角分析
精確解出的遞推式
合併長度為 和 的兩個序列至多需要 次比較,所以當 時,最壞比較次數滿足 ,。共 層,每層貢獻 減去該層的合併次數,而合併總共有 次,故
當 時為 ,與對全部 個輸入的窮舉檢查一致。因此 的階可以寫成帶有明確線性修正項的精確公式。
例題詳解
例題 1.1.5
(搜尋失敗也有正確性證明)
在 搜尋五。初始 的中點二含四,更新為 。中點四含九,得 ;中點三含八,得 ,返回失敗。不變量在每步排除被移去的位置,所以失敗是正確結果,並非例外狀態。
例題 1.1.6
(插入排序與不同時間界)
插入排序在第 次迭代開始時,保持長度 的前綴是原前綴的有序排列。把下一鍵插入並右移較大鍵,可保持此性質,最後排序全陣列。遞增輸入每次插入只需一次失敗比較,標準實作為線性。遞減輸入須移動 個鍵,最壞為二次。說插入排序是二次,描述的是最壞情況,而非每個輸入。
例題 1.1.7
(數值與二進制長度)
考慮從零數到正整數輸入 的迴圈。若 ,輸入有 位元,迴圈卻執行 次,對位元長度為指數。稱它線性,只有以數值 為參數才有意義,並未建立二進制整數上的多項式時間算法。若計數器的長度亦增長,位元運算計數還可能增加成本。
常見錯誤
反例模式
在未排序陣列上作二分搜尋
一個誘人的說法是:只要目標在陣列中出現,迴圈就能找到它。取 、。起初 、,中點 ,,故 。接著 ,,故 ,迴圈結束並返回 NOT_FOUND,然而 。失效的不變量步驟是對有序性的使用:「 排除所有不小於 的索引」只有在 非遞減時才成立,這裏它錯誤地丟棄了索引 。修正辦法就是前置條件本身:搜尋開始前,陣列必須按非遞減次序排列。
常見錯誤
(只證明成功的分支)
不變量必須涵蓋每個合法分支,包括相等與空輸入。只測成功搜尋,沒有證明失敗規格。終止證明應用有下界的量,不能只說搜尋區域改變。
常見錯誤
(把大 O 當成等式或最壞情況)
大 O 是上界,不是等式,也不是最壞情況的同義詞。常數函數也屬 ,只是這個界資訊不足。不同固定底數的對數只差常數因子,底數影響精確計數,卻不改變 分類。平均情況須指定輸入分佈,不能當作最壞保證。
總結
正確性需要規格、保持性及終止論證。時間需要成本模型、輸入大小與有理由的計數。二分搜尋縮小一個候選區間;合併排序處理兩半並付出組合成本。兩者雖同屬分治,遞推式卻反映不同的實際工作。
練習
快速檢查
(改為找第一個滿足 的索引,若無則返回 。給不變量並解釋更新。)
說明 以下及 以上(含)的索引應滿足甚麼。
解答 · 引導解答
保持所有小於 的索引值都小於 ,所有不小於 的索引值都至少為 ,以及 。起始外部區域均空。若 ,設 ,否則設 。有序性證明保持,區間長度如前嚴格減少。終止時 分隔兩區,故為第一個合格索引或 。相等時須走後一分支,保留較早的相等鍵。
快速檢查
(對二的冪及正常數基本成本,解 及 。)
數出遞歸的層數及每層的成本。
解答 · 答案
寫 ,第一式展開 次,得常數加 ,所以 時為 。第二式每個內層成本為 ,共有 層,另有 個常數成本葉節點,故為 。
快速檢查
(程式設計者說只檢查輸出有序便證明排序正確。給反例及缺少的後置條件。)
想想一個必然有序、卻毫無用處的算法。
解答 · 答案
對任何輸入均返回空陣列,輸出總有序,卻沒有保留輸入元素。缺少的是輸出須為輸入的排列,包含重數;只檢查長度仍會容許用不相關的相等鍵替代。
快速檢查
(給出 的明確常數,證明 。)
把 與 同 比較。
解答 · 答案
當 ,由 、,有 。下常數三、上常數十四、閾值一,證明所述 界。