算法中的循环不变式

社区广播:运维派(Yunweipai.com)是国内最早成立的IT运维社区,欢迎大家投稿,让运维人不再孤寂的成长!

算法导论中提出的循环不变式,计算机领域解决实际问题的强大方法,值得牢记。

数学基础

循环不变式的数学基础是是数学归纳法

数学归纳法范式

  1. 给定命题P(n)
  2. 证明当n=1时命题成立
  3. 证明如果在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
  • 不变式:对应到数学归纳法中的命题

在计算机语言中,通过循环维持命题一直为真,直至循环结束。

按照下面步骤,判断一个算法中的循环不变式的正确性:

  1. 初始状态:不变式的命题是否为真
  2. 维持不变式:是否维持了不变式继续为真
  3. 结束:循环是否正确的结束了

插入排序算法中的循环不变式

算法描述

从未排序的堆中获取一个数,与已排序的序列比较,插入到合适的位置。

以扑克牌为例子,每次从扑克牌堆中获取一张牌,与手中已经排好序的扑克牌比较,找到合适的位置插入到手中的排中。

循环不变式

对于给定的无序序列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)

代码参考

algorithm

网友评论comments

发表评论

电子邮件地址不会被公开。 必填项已用*标注

暂无评论

Copyright © 2012-2017 YUNWEIPAI.COM - 运维派 - 粤ICP备14090526号-3
扫二维码
扫二维码
返回顶部