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


当前回答

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

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

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

其他回答

Loop invariant is a mathematical formula such as (x=y+1). In that example, x and y represent two variables in a loop. Considering the changing behavior of those variables throughout the execution of the code, it is almost impossible to test all possible to x and y values and see if they produce any bug. Lets say x is an integer. Integer can hold 32 bit space in the memory. If that number exceeds, buffer overflow occurs. So we need to be sure that throughout the execution of the code, it never exceeds that space. for that, we need to understand a general formula that shows the relationship between variables. After all, we just try to understand the behavior of the program.

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

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

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

在线性搜索(根据书中给出的练习)中,我们需要在给定的数组中找到值V。

它很简单,从0 <= k < length开始扫描数组并比较每个元素。如果找到V,或者扫描到数组的长度,就终止循环。

根据我对上述问题的理解-

循环不变量(初始化): 在k - 1迭代中找不到V。第一次迭代,这是-1因此我们可以说V不在-1位置

保养: 在下一次迭代中,V不在k-1中成立

Terminatation: 如果V位于k个位置,或者k达到数组的长度,则终止循环。

值得注意的是,循环不变量可以帮助迭代算法的设计,因为它被认为是一个断言,表示变量之间的重要关系,在每次迭代开始时和循环结束时,这些关系必须为真。如果这是成立的,计算是在有效的道路上。如果为false,则算法失败。

对不起,我没有评论权限。

正如你提到的@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