algorithm - 循环不变功能

Question

我想知道循环不变量。我开始知道在算法（主要是排序算法）中有一个循环不变量，循环不变量表示算法的正确性。

这是如何运作的？有人可以帮助我理解这一点吗？

Answer 1

循环不变量本身并不表示算法的正确性。它是一个谓词，对于循环的每次迭代都是正确的。（您通常需要证明谓词对于循环确实是不变的。）然后可以使用不变量来证明循环的各种属性（可能包括正确性）。维基百科文章Loop invariant有一些例子展示了它是如何工作的。有关更多示例和解释，请参阅此线程。