算法導論第二章——算法基礎

1. 插入排序

我們的第一個算法，求解排序問題。

輸入：

n個數(shù)的一個序列< $a1,a2,...,an$ >

輸出:

輸入序列的一個排列 < $a1',a2',...,an'$ >,滿足 $a1'<=a2',...,<=an'$

我們也將希望排序的數(shù)稱為關(guān)鍵詞

我們首先介紹插入排序油狂，對于少量元素這是一個有效的算法案训。工作方式類似于撲克牌的排序，從桌子上拿走一張牌夸盟，并插入手牌中正確的位置，使得手牌總是排序好的像捶。從桌子上拿的牌也是牌堆中的第一張牌上陕。

python算法描述

def insertionSort(A):
    n = len(A)
    for j in range(1,n):
        key = A[j]
        i = j-1
        while i>=0 and A[i]>key:
            A[i+1] = A[i]
            i = i-1
        A[i+1] = key

循環(huán)不變式與算法的正確性

該圖表面對 $A=<5,2,4,6,1,3>$ 該算法的工作流程。下標j指出準備要插入手中的當前牌拓春，而 $A[1..j-1]$ 的子數(shù)組構(gòu)成了已排好序的牌释簿，剩余的數(shù)組對應于仍在桌子上的牌堆。我們把 $A[1..j-1]$ 所具有的性質(zhì)稱為循環(huán)不變式硼莽。即每次循環(huán)都有這種性質(zhì)庶溶。

運行圖解

循環(huán)不變式主要用于幫助我們理解算法的正確性。
關(guān)于循環(huán)不變式懂鸵，我們必須證明三條性質(zhì)：

初始化：循環(huán)的第一次迭代之前偏螺，它為真
保持：如果循環(huán)的某次迭代之前它為真，那么下次迭代之前仍為真
終止：在循環(huán)終止時匆光，不變式為我們提供一個有用的性質(zhì)套像，該性質(zhì)有助于證明算法是正確的。

一二兩條類似于數(shù)學歸納法终息，即相當于基本情況和歸納步夺巩，若證明成功贞让，即循環(huán)的每次迭代前循環(huán)不變式都為真。

第三條意味著我們將用循環(huán)不變式來證明正確性柳譬，通常喳张，我們和導致循環(huán)終止的條件一起使用循環(huán)不變式。

下面我們來看看美澳，對于插入排序證明這些性質(zhì)成立销部。

初始化

在第一循環(huán)( $j=2$ )之前，循環(huán)不變式成立制跟，因為子數(shù)組僅有單個元素構(gòu)成柴墩。

保持

我們給個非形式化的證明：
for循環(huán)中將 $A[j-1],A[j-2]..A[j-n]$ 等向右移動一個位置，直到 $A[j]$ 找到適當?shù)奈恢觅灬６髮?img class="math-inline" src="https://math.jianshu.com/math?formula=A%5Bj%5D" alt="A[j]" mathimg="1">插入該位置江咳，這時子元素仍由原來 $A[1..j]$ 的元素構(gòu)成，但已有序哥放。以此歼指，每次對j增加構(gòu)成的新子數(shù)組均有序。

終止

導致for循環(huán)終止的條件是 $j>A.length=n$ ,因此將j不斷加一時甥雕，必有j=n+1,在循環(huán)不變式表述中將j用n+1代替踩身，那么子數(shù)組由 $A[1..n]$ 的元素組成，但已排序社露，因此算法正確挟阻。

2.分析算法

分析算法的意味著預測算法需要的資源，我們最想度量的是時間峭弟。
為了分析算法附鸽，我們需要有一個實現(xiàn)技術(shù)的模型，包括描述所有資源及其代價的模型瞒瘸。我們使用一中假定的通用單處理器計算模型——隨機訪問機(RAM)坷备。在RAM中，指令一條接一條執(zhí)行情臭，沒有并發(fā)操作省撑。

我們要注意不能濫用RAM模型，RAM模型只能完成基本操作俯在，基本觀點是竟秫，計算機如何設計，RAM就如何設計跷乐。

RAM中的數(shù)據(jù)類型有整型和浮點型肥败，我們大部分情況下不關(guān)注精度，除非某些特殊應用。

在真實的計算機中還包含一些特殊指令拙吉，我們盡量避免這些指令潮孽。例如計算 $2^k$ 揪荣，當k較小時筷黔，我們當作常量時間計算。

我們在RAM模型中并不試圖對內(nèi)存層次進行建模仗颈。有些情況下會考慮內(nèi)存層次的影響佛舱，但是大部分情況下不會。

插入排序算法的分析

插入排序算法需要的時間依賴于輸入和被排序的程度挨决。一般來說请祖，算法的時間與輸入的規(guī)模同步增長，所以通常把一個程序的運行時間描述成其輸入規(guī)模的函數(shù)脖祈。

輸入規(guī)模的概念依賴于研究的問題肆捕，如排序問題中，是輸入的項數(shù)n盖高，整數(shù)相乘時慎陵，是整數(shù)的位數(shù)。對于圖喻奥，則使用頂點數(shù)和邊數(shù)來描述席纽。

一個算法在特定輸入上的運行時間是指執(zhí)行指令的操作次數(shù)。我們可以假定 $第i行代碼執(zhí)行的時間為ci$

如圖所示撞蚕，我們首先看看插入排序每條語句執(zhí)行的次數(shù)和時間润梯。注：while/for 等循環(huán)退出時會多執(zhí)行一次

插入排序.jpg

該算法的運行時間是每條語句的運行時間之和

我們對運行時間求和，得到

運行時間求和.jpg

當是最好情況下甥厦，即數(shù)組已經(jīng)排好序時纺铭，可以觀察到第6行，第七行不會被執(zhí)行刀疙，因此求和公式可更改為

最好情況求和.jpg

我們可以把該運行時間表示為

an+b

彤蔽，因此T(n)是n的線性函數(shù)。

當輸入已經(jīng)反向排序時庙洼，將導致最壞情況顿痪。我們必須將 $A[j]$ 和 $A[1..j-1]$ 中的每個元素相比較，因此得到求和公式

最壞情況.jpg

即T(n)為n的二次函數(shù)油够。

最壞情況與平均情況分析

在本書的其他部分蚁袭，我們往往集中于最壞情況運行時間分析，原因有三

最壞情況運行時間給出了上界石咬，知道了這個上界就能確保算法絕不需要更長的時間揩悄。
對某些算法，最壞情況經(jīng)常出現(xiàn)鬼悠。
平均情況往往和最壞情況大致一樣差

在某些特定情況下删性，我們會對算法的平均情況感興趣亏娜，我們將看到概率分析技術(shù)被用于各種算法。平均情況分析范圍有限蹬挺，對于特定的問題维贺，難以辨別什么才是平均情況。我們假設各種輸入具有相同的可能性巴帮，實際上該假設可能并不成立溯泣。

增長量級

我們真正感興趣的是運行時間的增長率或增長量級，所以我們只考慮公式中最重要的項榕茧。

3. 設計算法

我們可以選擇使用的算法設計技術(shù)有很多垃沦，插入排序使用了增量方法，本節(jié)我們將討論分治法用押，分治法的優(yōu)點之一是肢簿，通過一些特殊技術(shù)往往很容易確定其運行時間。

1. 分治

分治法思想：將原問題分解為幾個規(guī)模較小但類似原問題的子問題蜻拨，遞歸地求解子問題池充，再合并這些子問題的解來得到原問題的解。

分治模式在每層遞歸時通常都有三個步驟

分解原問題為若干子問題官觅，子問題為原問題的規(guī)模較小的實例
解決這些子問題纵菌，遞歸求解各子問題
合并這些子問題得到原問題的解。

歸并排序算法完全遵循該模式休涤，將n個元素分解為n/2個元素咱圆，使用歸并排序遞歸解決子數(shù)列，合并已排序的子數(shù)列得到答案功氨。

歸并排序的關(guān)鍵步驟是合并已排序好的子數(shù)列序苏，如兩個已排序好的數(shù)列 $A[p..q]和A[q+1..r]$ ，合并完成這兩個子數(shù)組得到新數(shù)組 $A[p..r]$

合并操作需要 $Θ(n)$ 的時間捷凄，我們不斷比較兩個子數(shù)組忱详，選取較小的元素放入新數(shù)組
中完成合并。

使用python代碼描述合并過程：

inf = float("inf")
def merge(A,p,q,r):
    L = A[p:q+1]#左邊的數(shù)組暫存
    R = A[q+1:r+1]#右邊的數(shù)組暫存
    L.append(inf)#插入哨兵
    R.append(inf)
    i = 0
    j = 0
    for k in range(p,r+1):#將數(shù)組合并到A中
        if L[i]<R[j]:
            A[k] = L[i]
            i+=1
        else:
            A[k] = R[j]
            j+=1

循環(huán)不變式為：

在for循環(huán)的每次迭代時跺涤，子數(shù)組 $A[p..k-1]$ 按從小到大的順序包含 $L[1..n1+1]$ 和 $R[1..n2+1]$ 中的 $k-p$ 個最小元素匈睁，進而， $L[i]$ 和 $R[j]$ 是各自所在數(shù)組中未被復制回數(shù)組A的最小元素桶错。
注:數(shù)組下標從1開始航唆，n1,n2分別為L和R的長度

接下來我們證明這個循環(huán)不變式:
初始化:

在循環(huán)的第一次迭代之前，有 $k=p$ ,因此 $A[p..k-1]$ 為空院刁，包含 $k-p=0$ 個最小元素糯钙，此時 $i=1,j=1$ ， $L[i]$ 和 $R[j]$ 是各自所在數(shù)組中未被復制回數(shù)組A的最小元素

保持：

為了理解每次迭代都維持循環(huán)不變式，我們先假設 $L[i]<=R[j]$ 任岸，此時 $L[i]$ 是未被復制回數(shù)組A的最小元素再榄。因為 $A[p..k-1]$ 包含k-p個最小元素，所以將 $L[i]$ 復制到A[k]之后享潜，子數(shù)組 $A[p..k]$ 將包含 $k-p+1$ 個最小元素困鸥，更新k值和i值后，即維持了原來的不等式成立米碰。

終止:

終止時 $k = r+1$ ,根據(jù)循環(huán)不變式 $A[p..k-1]$ 就是 $A[p..r]$ 且按照從小大大順序包含L和R中的k-p個最小元素窝革。
完整的歸并排序python代碼:

inf = float("inf")
def merge(A,p,q,r):
    L = A[p:q+1]
    R = A[q+1:r+1]
    L.append(inf)
    R.append(inf)
    i = 0
    j = 0
    for k in range(p,r+1):
        if L[i]<R[j]:
            A[k] = L[i]
            i+=1
        else:
            A[k] = R[j]
            j+=1
def mergeSort(A,lo,hi):
    if lo==hi:
        return
    mid = (lo+hi)//2
    mergeSort(A,lo,mid)
    mergeSort(A,mid+1,hi)
    merge(A,lo,mid,hi)

歸并排序圖示：

歸并.jpg

2. 分析分治算法

我們可以用遞歸方程或遞歸式來描述遞歸分治算法的運行時間购城。
分治算法運行時間的遞歸式來自于基本模式的三個步驟吕座，假設 $T(n)$ 是規(guī)模為n的一個問題的運行時間。
當問題規(guī)模足夠小時瘪板，則將運行時間寫作 $Θ(1)$ 吴趴。假設吧原問題分解成 $a$ 個子問題，每個子問題的規(guī)模是原問題的 $1/b$ 侮攀，求解 $a$ 個子問題就需要 $aT(n/b)$ 的時間锣枝。
如果分解成子問題需要時間 $D(n)$ ，合并時間為 $C(n)$ 兰英，那么得到遞歸式

遞歸式.jpg

歸并排序算法的分析

為了簡化分析撇叁，假定原問題的規(guī)模是2的n次冪
分解：分解為規(guī)模為 $n/2$ 的子問題，需要常量的時間畦贸， $Θ(1)$
解決：遞歸地求解兩個規(guī)模為 $n/2$ 的子問題陨闹，將貢獻 $2T(n/2)$ 的運行時間。
合并：合并需要 $Θ(n)$ 的時間薄坏。
因此得到遞歸式

歸并遞歸式.jpg

通過之后主定理的學習趋厉，我們會了解到該算法的時間復雜度為 $Θ(nlgn)$