循环不变式：把A[1...j-1]的这些性质形式表示为循环不变式。
循环不变式必须证明三条性质：
初始化：循环的第一次迭代之前，它为真；
保持：如果循环的某次迭代之前为真，那么下次迭代之前它仍为真；
终止：在循环终止时，循环不等式仍为真。
对于插入排序，看看如何证明这些性质成立：
初始化：首先证明第一次循环迭代之前(j=2时)，循环不变式成立。子数组A[1..j-1]仅由单个元素A[1]组成，实际上就是A[1]中原来的元素。而且该数组是排序好的。表明第一次循环迭代之前循环不变式成立。
保持：内部for循环将A[j-1]、A[j-2]、A[j-3]等向右移动一个位置，直到找到A[j]的适当位置，然后将A[j]的值插入该位置。此时A[1..j]由原来在A[1..j]中的元素组成，但已按序排列。
终止：导致for循环终止的条件是j>A.length=n。因为每次循环迭代j增加1，那么必有j=n+1。在循环不变式的表述中将j用n+1代替，有：子数组A[1..n]由原来在A[1..n]中的元素组成，但已排好序。
循环不等式与插入排序的正确性 循环不变式：把A[1...j-1]的这些性质形式表示为循环不变式。 循环不变式必须证...
程序员算法基础——贪心算法 程序员算法基础——贪心算法
HashMap部分源码 hash算法 可以看到hash算法计算分为三步 1.获得key的hash值2.在1的基础上...
最基础的收集算法 —— 标记/清除算法 之所以说标记/清除算法是几种GC算法中最基础的算法，是因为后续的收集...
Java基础：JVM垃圾回收算法 [toc] 参考：Java基础：JVM垃圾回收算法图解JVM垃圾回收算法 总结：...
程序员算法基础——动态规划 程序员算法基础——动态规划
理论基础部分： 人工智能基数算法简介 人工智能基础算法简介2 人工智能基础算法总结 TensorFlow 入门 T...
一、基础篇 1. Java基础知识 2. Java Web 3. JVM 4. 数据结构和算法 5. 网络安全 二...
算法基础--基础算法 前言：学校学完数据结构与算法后，感觉自己什么都没学到，唯一就知道好像有那么个东西，别说代码实...
1. 题目 2. 解答 详细解答方案可参考北京大学 MOOC 程序设计与算法（二）算法基础之动态规划部分。 从三角...
本文标题：2. 算法基础
本文链接：https://www.haomeiwen.com/subject/gdwhuqtx.html
网友评论