1.2 迭代不變式與正確性#

概念說明#

寫對一個迴圈靠的不是運氣，而是證明。核心工具是迭代不變式（loop invariant）：一個關於程式狀態的命題，滿足三個條件——

初始性：進入迴圈前，不變式成立。
維持性：若某一輪開始前成立，則一輪結束後仍成立。
終止性：迴圈結束時，不變式加上「結束條件」能推出我們要的答案。

這與數學歸納法同構：初始性是歸納基底，維持性是歸納步。差別在於迴圈會終止，所以我們還需一個遞減的良序量度（variant）——例如「剩餘元素個數」，證明迴圈不會跑個沒完。

以線性搜尋為例：不變式可取「前 \(i\) 個元素皆不等於目標」。進入迴圈前 \(i=0\) ，空集合性質顯然成立（初始性）；每輪檢查第 \(i\) 個元素，不等則 \(i{+}1\) ，性質保持（維持性）；迴圈結束時若 \(i=n\) ，代表全部元素都不是目標，回傳 -1 正確（終止性）。

更實用的例子是歐幾里得輾轉相除法。不變式：「 \(\gcd(a, b) = \gcd(\text{原}a, \text{原}b)\) 」。每輪 \((a, b) \leftarrow (b, a \bmod b)\) 不改變最大公因數（維持性），且 \(b\) 嚴格遞減（良序量度），最終 \(b=0\) 時 \(\gcd(a, 0) = a\) 即為答案（終止性）。三個條件湊齊，正確性無懈可擊。

養成「先寫不變式、再寫程式」的習慣，能讓迴圈的邊界條件（off-by-one 錯誤的根源）在設計階段就被抓出來，而不是靠測試碰運氣。

生活類比#

洗碗時的心理確認：「洗過的疊區沒有油污，未洗的堆疊只剩髒碗」。每洗完一個，兩句話都保持為真——這就是不變式；碗總數有限——這就是良序量度。

演算法步驟#

用不變式設計迴圈的工作流程：

想清楚迴圈結束時希望成立什麼命题。
把它「放寬」成進入迴圈前就成立的敘述（加上 \(i=0\) 之類的平凡條件）。
檢查迴圈主體能否維持該敘述。
找出一個每輪嚴格遞減的非負量度，確保終止。
寫程式，並用邊界案例（空輸入、單一元素）驗證。

Python 範例#

def gcd(a, b):
    # 不變式：gcd(a, b) == gcd(A, B)（A, B 為呼叫時的參數）
    # 量度：b 嚴格遞減且 >= 0，故必然終止
    while b != 0:
        a, b = b, a % b
    return a  # 終止時 b == 0，gcd(a, 0) == a

def linear_search(arr, target):
    # 不變式：arr[0:i] 中沒有 target
    i = 0
    while i < len(arr):
        if arr[i] == target:
            return i
        i += 1
    return -1

print(gcd(252, 105))          # 21
print(linear_search([3,7,9], 7))  # 1

複雜度與收斂性分析#

不變式證明的是「正確性」，複雜度分析則回答「多快終止」。歐幾里得法每兩輪至少讓 \(b\) 減半，故為 \(O(\log \min(a,b))\) 。線性搜尋量度 \(n - i\) 每輪減 1，共 \(n\) 輪， \(O(n)\) 。量度的遞減速度直接給出迭代次數上界——這是全書反覆出現的分析套路：找量度、估每輪縮小比例、換算成迭代次數。

練習#

為「計算 \(n!\) 的迭代版本」寫出不變式與量度，並逐步論證三條件成立。
二分搜尋的不變式是什麼？（提示：目標若存在，必在 lo..hi 區間內。）用它解釋為什麼 hi = mid - 1 與 hi = mid 兩種寫法需要不同的迴圈條件。
費波那契迭代版 a, b = b, a+b：寫出對應的不變式，並證明 \(k\) 輪後 \(a = F_k\) 。