首頁 編程技術算法中的循環不變式

算法中的循環不變式

運維派隸屬馬哥教育旗下專業運維社區,是國內成立最早的IT運維技術社區,歡迎關注公眾號:yunweipai
領取學習更多免費Linux云計算、Python、Docker、K8s教程關注公眾號:馬哥linux運維

算法導論中提出的循環不變式,計算機領域解決實際問題的強大方法,值得牢記。

數學基礎

循環不變式的數學基礎是是數學歸納法

數學歸納法范式

  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

本文鏈接:http://www.thecarconnectin.com/22644.html

網友評論comments

發表回復

您的電子郵箱地址不會被公開。

  1. 說道:

    你似乎將選擇排序理解成了冒泡排序

Copyright ? 2012-2022 YUNWEIPAI.COM - 運維派 京ICP備16064699號-6
掃二維碼
掃二維碼
返回頂部
国产曰批视频免费观看完|久久久一本精品99久久精品66直播|色天使色偷偷AV一区二区三区|国产色秀视频在线播放|亚洲欧洲免费三级网站