在计算机科学中， 循环不变量 （loop invariant），是一组在循环体内、每次迭代均保持为真的某种性质，通常被用来证明程序或算法的正确性。

理解循环不变量这个概念对我们理解算法过程，和解决算法问题有很大的帮助。下面参考《算法导论》，对循环不变量的概念进行详细的解释。

我们使用循环不变量帮助我们理解一个算法为什么是对的。对于一个给定的循环不变量，我们必须遵循以下三个属性：

• 初始化： 在循环的第一次迭代之前，循环不变量为真。
• 保持： 如果在循环的一次迭代之前循环不变量为真，那么在下一次迭代之前循环不变量同样为真。
• 终止： 当循环结束时，不变量能够提供我们有用的属性，用于帮助我们证实算法是正确的。

当保证前两个属性时，循环不变量在循环的任意迭代之前都满足。注意它与 数学归纳法 的相似性，当你想证明一个属性存在时，你需要证明一个基准和一个归纳步。相应的，我们第一次迭代之前保证不变量成立对应于一个基准，我们在每次迭代之间保证不变量成立对应于一个归纳步。

因为我们用循环不变量证明算法正确性，所以第三个属性或许是最重要的。通常， 我们必须保证在循环结束时“循环不变量”和“循环终止条件”同时成立。 这与数学归纳法有所不同。数学归纳法常采用无限的归纳步，而循环不变量的归纳往往随着循环的终止而结束。

接下来，我们通过 插入排序 算法来更好的理解循环不变量。
先贴代码（Go语言）

func insertionSort(nums []int) {
   j, n := 0, len(nums)
   for j < n {
      i := j - 1
      key := nums[j]
      for i >= 0 && nums[i] > key {
         nums[i+1] = nums[i]
      nums[i+1] = key
循环不变量： j之前（不包含nums[j]）的元素已经排好序（升序）。
 
初始化： j为0，表示目前排好序的子数组没有元素，不变式成立。
保持： 如果前一轮迭代j满足条件，则[0,j)范围内子数组的元素均为升序。当前迭代中nums[j+1]与子数组的元素从大到小进行对比。如果找到第一个比nums[j+1]小的元素，则在其后插入一个值为nums[j+1]的元素。因此在此次迭代结束后，[0,j+1)范围内子数组的元素均为升序，不变式成立。
终止： j不断递增，当j == n时，所有数组的元素均被遍历处理，此时[0,n)为升序，不变式成立。
 
经过以上三个属性的证明，可以最终得出整个输入数组nums为升序的结论，满足算法的目的，同时也验证了算法的正确性。
                                    前两天看到一篇介绍二分原理的帖子，想起了以前写二分法的事情。二分法看似简单，但实际写的时候却发现 +1 -1 的地方很容易弄错。幸好之前看过循环不变量的介绍。 所谓循环不变量，是指在循环过程中保持不变的量。具体取什么样的量呢？显然，pi之类的常量在任何循环中都保持不变，但对分析循环并没有用处。 因此，为便于分析，循环不变量一般会取一个关于循环中的变量 V 的布尔函数 F，在整个
                                    在计算机科学中，循环不变式（loop invariant，或循环不变量、循环不变条件，也有译作循环不变性），是一组在循环体内、每次迭代均保持为真的性质（表达式），通常被用来证明程式或伪码的正确性（有时但较少情况下用以证明算法的正确性）。简单说来，“循环不变式”是指在循环开始和循环中，每一次迭代时为真的性质。这意味着，一个正确的循环体，在循环结束时“循环不变式”和“循环终止条件”必须同时成立。
初始化：循环的第一次迭代之前，它为真。
保持：如果循环的某次迭代之前它为真，那么下次迭代之前它仍为真。
终止：在循环终止时，不变式为我们提供一个有用的性质，该性质有助于证明算法是正确的。
《算法导论（第3版）》里出现「循环不变量」的地方：插入排序、归并排序、快速排序、优先队列、单源最短路径、最小生成树、……
选择排序的循环不变量
循环不变的性质：区间nums
在选择排序算法中，我们可以写出循环不变的性质：区间nums[0…i)里保存了数组里最小的i个元素，并且nums中的元素按升序排列。无论是在循环的初始化、循环的过程中、循环的结束，这个循环不变性质都是恒定不变的。我们可以根据这个不变性质去设计算法、去让程序更有逻辑性等；
对二分法进行代码实现时，
当此循环满足以下条件，即：在任何循环开始前，语句S和C都为真，而且在循环结束后，S仍为真，那么S就是循环不变量。
循环不变量定理：已知一个循环和循环条件的guard condition G。命 I(n) 为循环不变式。如果下面四个条件为真，那么此循环是正确的：
Basic property: the pre-condition implies  I(0)
Induct
                                    循环不变量（loop invariant）是一个不变量，被用来证明循环的特点，更多地，算法使用循环 (usually 正确性)。非正式的说，一个循环不变量是指在循环开始和循环中每一次迭代时永远为真的量，这意味着在循环中和循环结束时循环不变量和循环终止条件必须同时成立。
以二分法为例：已知 A[1..n] 是单调递增的数列，求 A 中所有大于或等于target的值中，最小的那一个的序号。
                                    循环不变量（Loop Invariant Code Motion）
循环不变量（loop invariant）就是不会随着每轮循环改变的表达式，优化程序只在循环体外计算一次并在循环过程中使用。编译器的优化程序能找出循环不变量并使用“代码移动（code motion)”将其移出循环体。
#include <stdio.h>
#include <stdint.h>
                                    时间复杂度是一个动态的概念，它表示随着输入规模的增大，程序的运行时间增加的快慢。具体时间复杂度的表示法是使用大O表示法，求法如下：时间复杂度的极限定义如下：g(N)就是大O括号中的内容，f(N)就是具体的我们代码的复杂度，我们可以找出一个其上界即cg(N),这里c是一个常数对于时间复杂度来说并不重要。所以g(N)就是我们要求的时间复杂度。快速排序不同于归并排序，它虽然也是递归但是它并不是分治算法的思想而是减治算法。