我在读CLRS的《算法导论》。在第二章中,作者提到了“循环不变量”。什么是循环不变量?
当前回答
《如何思考算法》的定义,Jeff Edmonds著
循环不变式是放置在循环和循环顶部的断言 每次计算返回到循环的顶部时,这必须成立。
其他回答
在这种情况下,不变量意味着在每次循环迭代的某一点上必须为真条件。
在契约编程中,不变量是在调用任何公共方法之前和之后必须为真(通过契约)的条件。
对不起,我没有评论权限。
正如你提到的@Tomas Petricek
另一个较弱的不变式也是成立的,即i >= 0 && i < 10(因为这是连续条件!)”
为什么它是循环不变量?
我希望我没有错,据我理解[1],循环不变将在循环开始时为真(初始化),它将在每次迭代(维护)之前和之后为真,它也将在循环结束后为真(终止)。但是在最后一次迭代之后,i变成了10。因此,条件i >= 0 && i < 10变为假值并终止循环。它违反了循环不变量的第三个性质(终止)。
[1] http://www.win.tue.nl/~kbuchin/teaching/JBP030/notebooks/loop-invariants.html
在线性搜索(根据书中给出的练习)中,我们需要在给定的数组中找到值V。
它很简单,从0 <= k < length开始扫描数组并比较每个元素。如果找到V,或者扫描到数组的长度,就终止循环。
根据我对上述问题的理解-
循环不变量(初始化): 在k - 1迭代中找不到V。第一次迭代,这是-1因此我们可以说V不在-1位置
保养: 在下一次迭代中,V不在k-1中成立
Terminatation: 如果V位于k个位置,或者k达到数组的长度,则终止循环。
不变的意思是永不改变
这里循环不变量的意思是“发生在循环中的变量的变化(增加或减少)并没有改变循环条件,即条件是满足的”,因此循环不变量的概念就产生了
简单地说,循环不变量是对循环的每次迭代都成立的某个谓词(条件)。例如,让我们看一个简单的For循环,它是这样的:
int j = 9;
for(int i=0; i<10; i++)
j--;
在这个例子中,i + j == 9(对于每个迭代)是正确的。一个较弱的不变式也是成立的 I >= 0 && I <= 10。