什么是循环不变式？
我正在阅读“algorithm简介”CLRS。 作者在第2章（插入sorting）中讨论了循环不variables。 我不知道这意味着什么。
简而言之，循环不变是一些谓词（条件），适用于循环的每一次迭代。 例如，让我们看看一个简单的for循环，看起来像这样：
int j = 9; for(int i=0; i<10; i++) j--;
在这个例子中，对于每一个迭代来说，它是正确的。 一个较弱的不variables也是正确的，即i >= 0 && i < 10 （因为这是继续条件！）或者j <= 9 && j >= 0 。
我喜欢这个非常简单的定义：（ 来源 ）
循环不变是在循环的每一次迭代之前和之后必然是真的[程序variables之间的]条件。 （请注意，这在迭代过程中没有涉及其真实性或虚假性。）
循环不变式本身并没有太大的作用。 但是，给定一个适当的不variables，它可以用来帮助certificatealgorithm的正确性。 CLRS中的简单例子可能与sorting有关。 例如，让你的循环不变是类似的，在循环的开始，这个数组的第一个条目被sorting。 如果可以certificate这确实是一个循环不variables（即它在每个循环迭代之前和之后都保持不变），则可以使用它来certificatesortingalgorithm的正确性：在循环结束时，循环不variables仍然满足，而计数器i是数组的长度。 因此，第一个条目被sorting意味着整个数组被sorting。
一个更简单的例子： 循环不variables，正确性和程序派生 。
我理解循环不变的方式是作为一个系统的，正式的工具来推理程序。 我们做了一个我们专注于certificate真实的陈述，我们称之为循环不变式。 这组织我们的逻辑。 虽然我们也可以非正式地争论一些algorithm的正确性，但是使用循环不变式迫使我们仔细考虑并确保我们的推理是密不透风的。
有许多人在处理循环和不variables时不会马上意识到这一点。 他们混淆了循环不变和循环条件（控制循环终止的条件）。
正如人们指出的，循环不变必须是真实的
- 在循环开始之前
- 在循环的每次迭代之前
- 循环结束后
（尽pipe在循环体中它可能暂时是错误的）。 另一方面，在循环结束后，循环条件 必须为假，否则循环将永远不会终止。
因此循环不变和循环条件必须是不同的条件。
二进制search是复杂循环不变的一个很好的例子。
bsearch(type A[], type a) { start = 1, end = length(A) while ( start <= end ) { mid = floor(start + end / 2) if ( A[mid] == a ) return mid if ( A[mid] > a ) end = mid - 1 if ( A[mid] < a ) start = mid + 1 } return -1 }
所以循环条件看起来非常简单 – 当start> end时循环终止。 但为什么这个循环是正确的？ 什么是certificate它是正确的循环不variables？
不variables是逻辑表述：
if ( A[mid] == a ) then ( start <= mid <= end )
这个陈述是一个逻辑重言式 – 在我们试图certificate的特定循环/algorithm的背景下总是如此。 它提供有关循环在终止后的正确性的有用信息。
如果我们返回是因为我们在数组中find了这个元素，那么这个语句显然是正确的，因为如果A[mid] == a则a在数组中，而mid必须在开始和结束之间。 如果循环终止，因为start > end那么不能有数字，例如start <= mid 和 mid <= end ，因此我们知道语句A[mid] == a必须是false。 然而，结果是整体的逻辑表述在空值意义上仍然是正确的。 （在逻辑中，if（false）then（something）永远是真的。）
现在我说什么关于循环条件一定是假的时候循环终止？ 它看起来像在数组中find元素时，循环条件为真时，循环终止！ 实际上不是，因为隐含的循环条件实际上是while ( A[mid] != a && start <= end )但是由于隐含了第一部分，所以我们缩短了实际的testing。 无论循环如何终止，该条件在循环后显然都是错误的。
先前的答案已经以很好的方式定义了一个循环不变式。
现在让我试着解释CLRS的作者如何使用Loop Invariants来certificateInsertion Sort的正确性 。
插入sortingalgorithm （如书中所示）：
INSERTION-SORT(A) for j ← 2 to length[A] do key ← A[j] // Insert A[j] into the sorted sequence A[1..j-1]. i ← j - 1 while i > 0 and A[i] > key do A[i + 1] ← A[i] i ← i - 1 A[i + 1] ← key
在这种情况下循环不变（来源：CLRS书）：子数组[1到j-1]总是sorting。
现在让我们检查一下，certificatealgorithm是正确的。
初始化 ：在第一次迭代之前j = 2。 所以Subarray [1：1]是要testing的数组。因为它只有一个元素，所以它是sorting的，所以不变是满足的。
维护 ：通过在每次迭代之后检查不variables，可以容易地validation这一点。在这种情况下，它是满意的。
终止 ： 这是我们将certificatealgorithm正确性的一步。
当循环结束时，j = n + 1的值。 循环不变满足。这意味着子数组[1到n]应该sorting。
这是我们想要用我们的algorithm做什么。因此我们的algorithm是正确的。
除了所有的好的答案之外，我想杰夫·埃德蒙兹（Jeff Edmonds）的一个很好的例子就是如何思考algorithm，可以很好地说明这个概念：
例1.2.1“查找最大双指algorithm”
1）规格：input实例由元素列表L（1..n）组成。 输出由一个索引i组成，使得L（i）具有最大值。 如果有多个具有相同值的条目，则返回其中的任何一个。
2）基本步骤：你决定使用双指法。 你的右手指在名单上。
3）进度测量：进度的衡量标准是你的右手手指的距离。
4）循环不变式：循环不变式表示您的左手指指向您的右手指迄今遇到的最大条目之一。
5）主要步骤：每次迭代，你的右手指在列表中移动一个条目。 如果您的右手指正指向一个大于左手指入口的入口，则将左手指移至右手指。
6）进步：因为你的右手指移动了一个条目，所以你取得了进步。
7）保持循环不变：你知道循环不变已经被保持如下。 对于每一步，新的左手指元素是Max（旧的左手指元素，新的元素）。 由循环不variables，这是最大（最大（较短列表），新元素）。 math上，这是最大（更长的列表）。
8）build立循环不变：你首先通过将两个手指指向第一个元素来build立循环不variables。
9）退出条件：当右手指完成遍历列表时完成。
10）结束：最后，我们知道问题解决如下。 通过退出条件，您的右手指已经遇到了所有的条目。 通过循环不变，你的左手指向这些最大值。 返回这个条目。
11）终止和运行时间：所需的时间是列表长度的一些常数。
12）特殊情况：当有多个条目具有相同的值或当n = 0或n = 1时，检查会发生什么情况。
13）编码和实施细节：…
14）formscertificate：algorithm的正确性来自上述步骤。
在这种情况下不变是指在每个循环迭代中的某个点必须为真的条件。
在合约编程中，不变式是在任何公共方法被调用之前和之后必须是真实的（通过契约）的条件。
应该注意的是，当循环不variables可以帮助devise迭代algorithm时，如果在每次迭代开始时以及循环终止时都必须表示variables之间的重要关系。 如果这成立，那么计算正在走向有效性的道路上。 如果为false，则algorithm失败。
不变的意义永远不会改变
这里的循环不变意味着“循环中发生的变化（递增或递减）不会改变循环条件，即条件满足”，所以循环不变概念已经出现
很难跟踪循环发生的事情。 在没有实现其目标行为的情况下不终止或终止的循环是计算机编程中的常见问题。 循环不变式的帮助。 循环不变是关于你的程序中的variables之间的关系的正式声明，它在循环运行（build立不变）之前保持为真，并且在循环的底部再次为真，每次通过循环（保持不变）。 以下是代码中使用循环不variables的一般模式：
… //循环不变必须在这里
while（TEST CONDITION）{
//循环的顶部
…
//循环的底部
//循环不变必须在这里
}
//终止+循环不变=目标
…
在循环的顶部和底部之间，车头大概正在朝着循环的目标被制造。 这可能会干扰（使虚假）的不variables。 循环不variables的重点是每次重复循环体之前不variables的恢复。 这有两个好处：
工作不会以复杂的，依赖数据的方式进行到下一个阶段。 每个人都独立于所有其他人之间，通过这个循环，以不变的方式把这些传递连接在一起成为一个工作的整体。 推理你的循环的工作原理是减less到推理循环不变是每次通过循环都恢复。 这将循环的复杂整体行为分解成简单的小步骤，每个步骤都可以分开考虑。 循环的testing条件不是不variables的一部分。 这是什么使循环终止。 你分别考虑两件事情：为什么循环应该终止，为什么循环在终止时达到目标。 如果每次通过循环移动到满足终止条件，循环将终止。 确保这一点很容易：例如，将计数器variables加1，直到达到固定的上限。 有时终止的理由比较困难。
应创build循环不变式，以便达到终止条件，且不variables为真时，达到目标：
不变+终止=>目标
它需要创造性地创造简单而且相互关联的不variables，这些不variables捕捉除了终止以外的所有目标达成。 最好用math符号来表示循环不variables，但是当这导致过度复杂的情况时，我们依靠清晰的散文和常识。
对不起，我没有评论权限。
@托马斯·佩特里切克，你提到
一个更弱的不variables也是如此，i> = 0 && i <10（因为这是继续条件！）“
它如何是一个循环不变？
我希望我没有错，据我所知[1] ，循环不变将在循环的开始（初始化）是真实的，在每个迭代（维护）之前和之后将是真实的， 它也将是真实的循环的终止（终止） 。 但是在最后一次迭代之后，我变成了10.因此，条件i> = 0 && i <10变成了假并终止了循环。 它违反了循环不变的第三个属性（终止）。
[1] http://www.win.tue.nl/~kbuchin/teaching/JBP030/notebooks/loop-invariants.html
循环不变属性是一个条件，适用于循环执行的每一步（即循环，while循环等）
这对于循环不变certificate是必不可less的，在这个certificate中，如果在执行这个循环不变属性的每一个步骤中都能够正确地执行algorithm。
为了使algorithm正确，循环不变式必须保持在：
初始化 （开始）
维护 （每一步之后）
终止 （完成时）
这是用来评估一堆东西，但最好的例子是加权图遍历的贪心algorithm。 对于一个贪婪的algorithm来产生一个最佳的解决scheme（一个通过图的path），它必须达到连接所有可能的最低权重path上的所有节点。
因此，循环不变性质是所采用的path权重最小。 在开始我们没有添加任何边缘，所以这个属性是真实的（在这种情况下，这不是错误的）。 在每一步中 ，我们都遵循最低权重边缘（贪婪步骤），所以我们再次采取最低权重path。 最后 ，我们find了加权最小的path，所以我们的属性也是如此。
如果algorithm不这样做，我们可以certificate它不是最优的。
循环不变是一个math公式，如(x=y+1) 。 在这个例子中， x和y代表一个循环中的两个variables。 考虑到代码执行过程中这些variables的变化，几乎不可能testing所有可能的x和y值，看看它们是否会产生任何错误。 可以说x是一个整数。 整数可以容纳32位的内存空间。 如果该数字超过，则会发生缓冲区溢出。 所以我们需要确保在执行代码的过程中，它永远不会超出这个空间。 为此，我们需要了解显示variables之间关系的一般公式。 毕竟，我们只是试图了解程序的行为。
简而言之，在每个循环迭代中都是一个LOOP条件：
for(int i=0; i<10; i++) { }
在这里我们可以说i的状态是i<10 and i>=0
在线性search（按照书中给出的练习），我们需要在给定的数组中find值V.
它简单的扫描数组从0 <= k <长度和比较每个元素。 如果find了V，或者如果扫描到达数组的长度，就结束循环。
根据我对上述问题的理解，
循环不variables（初始化）：在k-1次迭代中找不到V。 非常第一次迭代，这将是-1，因此我们可以说V没有find位置-1
维护：在下一次迭代中，在k-1中找不到V
终止：如果V在k位置或k到达数组的长度，终止循环。
