算法基础-循环不变量(loop invariant)
【摘要】 Promise.All() Promise.all()关注多个Promise对象的状态变化,传入多个Promise实例，包装成一个新的Promise实例返回。 <!DOCTYPE html><html lang="en"><head> <meta charset="UTF-8"> <meta http-equiv="X-UA-Compatible" content="I...
在计算机科学中，循环不变式（loop invariant，或循环不变量、循环不变条件，也有译作循环不变性），是一组在循环体内、每次迭代均保持为真的性质（表达式），通常被用来证明程式或伪码的正确性（有时但较少情况下用以证明算法的正确性）。简单说来，“循环不变式”是指在循环开始和循环中，每一次迭代时为真的性质。这意味着，一个正确的循环体，在循环结束时“循环不变式”和“循环终止条件”必须同时成立。
--维基百科
循环不变量或者叫循环不变性也是证明算法的正确性的一种方法，《算法导论》中提到利用循环不变量整懵算法正确应该满足3个条件：
- 初始条件：首次循环前不变性成立
- 保持条件：一次循环前不变性如果成立，则下次循环开始前不变性成立
- 终止条件：循环结束后，循环不变性应能表明程序的正确性
循环不变式的书写方法：
- 定义循环不变式，并在循环体每次结束后保持循环不变式
- 先一般，后特殊
- 每次必须向前推进循环不变式中涉及的变量值
- 每次推进的规模必须为1
【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）