我在读CLRS的《算法导论》。在第二章中,作者提到了“循环不变量”。什么是循环不变量?


当前回答

简单地说,它是一个循环条件,在每次循环迭代中都为真:

for(int i=0; i<10; i++)
{ }

在这里,我们可以说i的状态是i<10并且i>=0

其他回答

不变的意思是永不改变

这里循环不变量的意思是“发生在循环中的变量的变化(增加或减少)并没有改变循环条件,即条件是满足的”,因此循环不变量的概念就产生了

简单地说,循环不变量是对循环的每次迭代都成立的某个谓词(条件)。例如,让我们看一个简单的For循环,它是这样的:

int j = 9;
for(int i=0; i<10; i++)  
  j--;

在这个例子中,i + j == 9(对于每个迭代)是正确的。一个较弱的不变式也是成立的 I >= 0 && I <= 10。

《如何思考算法》的定义,Jeff Edmonds著

循环不变式是放置在循环和循环顶部的断言 每次计算返回到循环的顶部时,这必须成立。

循环不变量是在循环执行前后为真的断言。

在这种情况下,不变量意味着在每次循环迭代的某一点上必须为真条件。

在契约编程中,不变量是在调用任何公共方法之前和之后必须为真(通过契约)的条件。