Python - 演算法證明

為了證明一個演算法的效率，我們需要一些數學工具作為證明。這些工具幫助我們對演算法的效能和準確性提供一個數學上令人滿意的解釋。下面列出了一些可以用來證明一個演算法優於另一個演算法的數學工具。

• 直接證明 − 透過直接計算來直接驗證陳述。例如，兩個偶數的和始終是偶數。在這種情況下，只需將要研究的兩個數字相加，並驗證結果為偶數。

• 歸納法證明 − 我們從一個特定例項的真理開始，然後將其推廣到所有屬於真理的可能值。這種方法是採用一個已驗證真理的案例，然後證明對於相同給定條件下的下一個案例也成立。例如，所有形式為 2n-1 的正數都是奇數。我們證明它對於某個 n 值成立，然後證明它對於下一個 n 值也成立。這透過歸納法證明了該陳述通常是正確的。

• 反證法 − 這個證明基於條件：如果非 A 蘊含非 B，則 A 蘊含 B。一個簡單的例子是：如果 n 的平方是偶數，則 n 必須是偶數。因為如果 n 的平方不是偶數，則 n 不是偶數。

• 窮舉法 − 這類似於直接證明，但它是透過分別訪問每個情況並證明每個情況來建立的。這種證明的一個例子是四色定理。