---
title: 演算法介紹|第二週
tags: 資料結構與演算法
---

# 演算法正確性證明

## 找出(迴圈)不變性 / (loop)invariant

也就是演算法在迴圈中所保持恆定的部分
以上課的「找最小值」的例子來說，不變的性質就是
「第 k 次迴圈結束時，A~mk~ 的值一定小於等於 A~1~ 到 A~k~」

## 證明方法 - 歸納法 Induction

老朋友了，說明到了第 t 個都是正確的，證明第 t+1 個
也是正確的，最後得出上面那點的結論

寫法就是：

:::success
根據數學歸納法，這個不變性質從 i = 2 ~ k 恆定；
所以當迴圈結束在第 k 次時，某某某結論保持正確
>以上面的例子的話結論就是
>A\[mk\] ≤ A\[j\] for j = 1, 2, . . . , k

:::