算法导论中提出的循环不变式，计算机领域解决实际问题的强大方法，值得牢记。
数学基础
数学归纳法范式
- 给定命题P(n)
- 证明当n=1时命题成立
- 证明如果在n=m时命题成立，那么可以推导出在n=m+1时命题也成立
数学归纳法的原理在于：首先证明在某个起点值时命题成立，然后证明从一个值到下一个值的过程有效。当这两点都已经证明，那么任意值都可以通过反复使用这个方法推导出来。
举例证明
命题
假设我们要证明下面这个公式（命题）：
1+2+3+…+n=/frac{n(n+1)}{2}
证明
第一步：n=1时命题成立
1=/frac{1(1+1)}{2}
第二步：假设n=m时命题成立
1+2+3+…+m=/frac{m(m+1)}{2}
第三步：证明n=m+1时命题成立
1+2+3+…+m+(m+1)=/frac{m(m+1)}{2}+(m+1)
上面等式运算最终得到如下等式：
1+2+3+…+m+(m+1)=/frac{(m+1)((m+1)+1)}{2}
令k=m+1，则上面等式变为：
1+2+3+…+(k-1)+k=/frac{k(k+1)}{2}
这个等式符合第二步的假设，证明完毕。
计算机语言中的循环不变式
计算机语言中的循环不变式由两部分组成：循环，不变式 。
- 循环：对应到数学归纳法中的1…n
- 不变式：对应到数学归纳法中的命题
在计算机语言中，通过循环维持命题一直为真，直至循环结束。
按照下面步骤，判断一个算法中的循环不变式的正确性：
- 初始状态：不变式的命题是否为真
- 维持不变式：是否维持了不变式继续为真
- 结束：循环是否正确的结束了
插入排序算法中的循环不变式
算法描述
从未排序的堆中获取一个数，与已排序的序列比较，插入到合适的位置。
以扑克牌为例子，每次从扑克牌堆中获取一张牌，与手中已经排好序的扑克牌比较，找到合适的位置插入到手中的排中。
循环不变式
对于给定的无序序列A[1…n]，算法中的不变式为已经排好序的序列A[1…i]。
当i=1时，不变式A[1]是已经排序好的（因为只有一个元素），命题成立。
算法中的循环需要保持当i=k时，A[1…k]仍然是排序好的，则当循环结束，i=n时，A[1…n]是一个排序好的序列。
伪代码
1 2 3 4 5 6 7 8 |
for i =0 to n:
j = i - 1
next = A[j]
while j > 0 and A[j] > next:
A[j+1] = A[j] #大的数网后移动，空出位置j给next
j--
A[j+1]=next
i++
|
python代码
1 2 3 4 5 6 7 8 9 10 11 12 13 |
def insertion_sort(A):
length = len(A)
if length < 2:
return
i = 0
while i < length:
j = i - 1
next = A[i]
while j >= 0 and A[j] > next:
A[j+1] = A[j]
j = j - 1
A[j+1] = next
i = i + 1
|
选择排序算法中的循环不变式
算法描述
在一堆未排序的数中，假设为A[1…n]，选择一个最小的，放到A[1]的位置，再选择一个第二小的，放到A[2]的位置。重复上述操作直至所有的数被选择完成，完成排序。
循环不变式
对于给定的无序序列A[1…n]，算法中的不变式为A[1…i]，A[1…i]为每次从无序序列中找出的最小的值组成。
当i=1时，A[1]是从A[1…n]中找到的最小值，不变式成立。算法中需要保持A[1…k]一直是从A[k,n]中找到的最小值，当k=n时，A[1…n]是排序的序列。
伪代码
1 2 3 4 |
for i = 0 to n:
for j = i to n:
# 从i到n序列中找到一个最小值所在位置k
# 交换A[i]与A[k]的值
|
python代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
def selection_sort(A):
n = len(A)
if n < 2:
return
i = 0
while i < n:
min = A[i]
k = i
j = i + 1
while j < n:
if A[j] < min:
min = A[j]
k = j
j = j + 1
tmp = A[i]
A[i] = A[k]
A[k] = tmp
i = i + 1
|
冒泡排序算法中的循环不变式
算法描述
给定一个无序序列A[1…n]，选定第一个与后面所有值比较，如果比当前值小，则将小的值与当前值交换；依次遍历整个序列，完成排序。
循环不变式
算法中的不变式为A[1…i]，当i=1时，遍历剩余n-1个元素与A[1]比较，如果A[k]>A[1]，则交换他们两的值，此时A[1]是序列中的最小值。算法中维持此不变式，那么当i＝n是整个序列排序完毕。
伪代码
1 2 3 4 |
for i = 0 to n:
for j = i to n:
if A[i] > A[j]:
swap(A[i], A[j])
|
python代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
def bubble_sort(A):
n = len(A)
if n < 2:
return
i = 0
while i < n:
j = i
while j < n:
if A[i] > A[j]:
tmp = A[i]
A[i] = A[j]
A[j] = tmp
j = j + 1
i = i + 1
|
归并排序算法中的循环不变式
算法描述
归并排序使用递归的方法实现。假设无序的序列A[p…q]被排序为了两个子序列：A[p…r], A[r…q]，那么最终的有序序列需要将这两个字序列排序，排序方法为：从两个序列分别取一个值，比较大小，合并到最终的序列中，直至两个序列最终合并为一个序列。
循环不变式
合并算法过程中的不变式为A[p…k]，A[p…k]的值由两个字序列逐个元素比较后得到，过程中保持A[p…k]始终是排序后的序列，那么当k=q时整个序列就是排序好的。
伪代码
合并算法分为两部分：合并，递归。
合并部分伪代码
1 2 3 4 5 6 |
merge(A, p, r, q):
left = A[p:r]
right = A[r:q]
#如果left不为空，right为空，则将left所有元素合并到A
#如果right不为空，left为空，则将right所有元素合并到A
#否则，逐个比较left与right的元素，合并到A
|
递归部分伪代码
1 2 3 4 5 6 |
merge_sort(A, p, q):
r = (p+q)/2
if q-p > 1:
merge_sort(A, p, r)
merge_sort(A,r,q)
merge(A, p, q)
|
python代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
def _merge(A, p, r, q):
left = A[p:r]
right = A[r:q]
# 结束标记
left.append(None)
right.append(None)
k = p
i = j = 0
while k < q:
if left[i] is None and right[j] is not None:
A[k] = right[j]
j = j + 1
k = k + 1
continue
if right[j] is None and left[i] is not None:
A[k] = left[i]
i = i + 1
k = k + 1
continue
if left[i] < right[j]:
A[k] = left[i]
i = i + 1
else:
A[k] = right[j]
j = j + 1
k = k + 1
def merge_sort(A, p, q):
if q - p > 1:
r = (p + q)/2
merge_sort(A, p, r)
merge_sort(A, r, q)
_merge(A, p, r, q)
|
代码参考
本文链接：http://www.yunweipai.com/22644.html
原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/tech/pnotes/53241.html