循环不变式(loop invariant)

循环不变式,是指让每次循环都成立的逻辑表达式,用于证明整个算法的正确性。

它通过证明循环体三条性质的正确性来证明整个算法的正确性。

三条性质:
初始化:循环的第一次迭代前,循环不变式为真。
即初始化的数据结构与原始数据都是正确的。
保持:如果某次迭代前它为真,那么下次迭代之前它仍为真。
即每次迭代都保证正确的处理。
终止:在循环终止时,不变式为我们提供一个有用的性质,该性质有助于证明算法是正确的。
即研究在循环终止时发生了什么,并对循环结果进行判断。

在实际写算法的过程中,我们可以选择非形式化地通过分析循环不变式的真假来保证算法的正确性,也可以通过设置布尔值,并在每次循环前都利用某种判定规则得出布尔值并进行判断,来保证算法的正确性。

References:
《算法导论》第3版第10,11页
图灵社区-循环不变式

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • Java虚拟机(Java Virtual Machine)简称JVM Java虚拟机是一个想象中的机器,在实际的计...
    磨砺营IT阅读 365评论 0 7
  • 写在前面 关于Git的使用,网上的教程很多,这里推荐一个廖雪峰教程,写的很详细,而且图文并茂,推荐推荐。不想看这个...
    林里icer阅读 506评论 0 0
  • 年又过年,相信很多姑娘过年回到家都会被长辈催婚,介绍对象,逼着相亲。 这个时候多少会焦虑,烦恼,反感!但是其实不必...
    夜未秧歌阅读 346评论 2 5
  • 现在是2018.8.9,中午11.55,在机场候机写下两周的督导日记。 时间:2018.7.26-8.7 地点:马...
    饭饭_bms阅读 433评论 0 0
  • 但逢新旧岁之交,传说中年兽在这天会出来作恶。有一次它跑到村庄里为非作歹,被一家门口晾的 大红衣服 吓跑了。 到了另...
    fee铖阅读 230评论 0 0