循环不变式:算法中基础概念的明晰

循环不变式 循环不变式主要用来辅助我们理解算法的正确性,对于循环不变式,必须证明它的三个性质 初始化:它在循环的第一轮迭代开始之前,应该是正确的。保持:如果在某一次循环迭代开始之前是正确的,那么在下一次迭代开始之前,它也应该保持正确(假设当循环变量等于k时符合,再看执行一遍循环体后是否还符合循环不变式)。结束:当循环结束时,不变式给了我们一个有用的性质,它有助于表明算法是正确的(这一步是和数学归纳法不同的一点,用循环不变式则更进一步,数学归纳法到这里就得出了一个关系式就结束,而用循环不变式,不但要先确保一个正确的关系式,还要看最后循环结束时,循环变量最后等于多少,根据循环不变式推导是否符合自