循环不变量

1、循环开始时需要做什么?

之前我们讲的线性查找法的核心代码如下:

public static <E> int search(E [] data,E target){
    for (int i = 0; i < data.length; i++)
        if (data[i].equals(target))
            return i;
    return -1;
}

我们是否有思考过,这样一个简单的查找算法,用到了循环,但是每一轮循环开始前,需要满足的条件是什么?

扎实打牢数据结构算法根基,从此不怕算法面试系列之006 week01 02-06 循环不变量-LMLPHP

扎实打牢数据结构算法根基,从此不怕算法面试系列之006 week01 02-06 循环不变量-LMLPHP

其实,循环开始时,需要确认:
确认data[i]是否是目标
通过语句,if (data[i].equals(target))判断

循环体执行完一次时:
我们确认了data[i]不是目标,换句话,即:data[0…i]中没有找到目标。

扎实打牢数据结构算法根基,从此不怕算法面试系列之006 week01 02-06 循环不变量-LMLPHP

注:方括号[]表示的时闭区间,圆括号()表示的是开区间。
闭区间包含开闭的元素,开区间不包含开闭的元素。
也可以半开半闭,即:(],或者[)。
即:data[0…i],也可以表示为data[0…i-1)

2、什么是循环不变量?

什么是循环不变量呢?
循环不变量定义:即每一轮循环开始时,循环都满足的性质或者条件。

扎实打牢数据结构算法根基,从此不怕算法面试系列之006 week01 02-06 循环不变量-LMLPHP

3、循环不变量的作用

循环不变量的作用,其实如定义所讲,帮助我们厘清每一轮循环开始时循环所处的条件。有助于厘清算法实现的思路。
扎实打牢数据结构算法根基,从此不怕算法面试系列之006 week01 02-06 循环不变量-LMLPHP

在循环中,循环体的作用,就是维持循环不变量。

循环体和循环不变量的关系,本身也是”证明“算法正确性的一种方式。
这里的”证明“用了引号,因为并不是严谨的数学证明。

扎实打牢数据结构算法根基,从此不怕算法面试系列之006 week01 02-06 循环不变量-LMLPHP

其实,每次循环开始时,满足一个条件,
即:data[0……i-1]中没有找到目标。

总结重点:
写出正确的代码,需要定义清楚循环不变量,循环体的作用就是为了维持循环不变量。

扎实打牢数据结构算法根基,从此不怕算法面试系列之006 week01 02-06 循环不变量-LMLPHP

04-17 23:58