開篇語

今天開始看《算法導(dǎo)論》的第二章--算法基礎(chǔ)，主要內(nèi)容是講述了循環(huán)不變式以及排序算法的設(shè)計(jì)以及復(fù)雜度的計(jì)算，文中巧妙地運(yùn)用了撲克牌的插牌來形象的表達(dá)了排序算法的內(nèi)在內(nèi)容，十分的生動(dòng)形象。

撲克牌抓牌解釋排序算法

正文

一、插入算法

循環(huán)不變式三性質(zhì)：

1. 初始化（循環(huán)第一次迭代之前）的時(shí)候，它為真；

2. 如果循環(huán)的某次迭代之前它為真，那么下次迭代之前它仍為真；
3. 循環(huán)結(jié)束的時(shí)候，不變式為我們提供一個(gè)有用的性質(zhì)，該性質(zhì)有助于證明算法是正確的。

三性質(zhì)

偽代碼的一些規(guī)定：

還有一部分就不做多的描述了。大家有興趣的自己網(wǎng)購算法導(dǎo)論或者去圖書館借閱都可以

排序中的插入算法：

INSERTION-SORT(A)   #A是一個(gè)等待排序的數(shù)組
1    for j=2 to A.length
2      key=A[j]
3      //Insert A[j] into the sorted qequence A[1..j-1]      #把數(shù)組中的第j個(gè)數(shù)字取出來
4      i=j-1
5      while i>0 and A[i]>key   //取出已經(jīng)排好的前面的，如果滿足取出的數(shù)大于小于之排好的數(shù)，那么進(jìn)入循環(huán)
6          A[i+1]=A[i]
7          i=i-1   //將大的數(shù)放到高序號，然后再次對更加之前的數(shù)進(jìn)行比較。
8       A[i+1]=key

插入算法

插入算法如果類比到插牌的過程中，那么就是類似一把牌，按照從左到右大小的順序排好，那么每抽上來一只牌，都與目前最右邊的進(jìn)行比較， 如果比它大，那么就放在最右邊；如果比它小，那么就與右邊數(shù)過來第二張進(jìn)行比較。直到找到比它小的那張牌，就插在那張牌的右邊。

循環(huán)不變式與插入排序的正確性

算法的復(fù)雜度分析

定義：如果一個(gè)問題的規(guī)模是n，解這一問題的某一算法所需要的時(shí)間為T(n)，它是n的某一函數(shù) T(n)稱為這一算法的“時(shí)間復(fù)雜性”。

當(dāng)輸入量n逐漸加大時(shí)，時(shí)間復(fù)雜性的極限情形稱為算法的“漸近時(shí)間復(fù)雜性”。

我們常用大O表示法表示時(shí)間復(fù)雜性，注意它是某一個(gè)算法的時(shí)間復(fù)雜性。大O表示只是說有上界，由定義如果f(n)=O(n)，那顯然成立f(n)=O(n^2)，它給你一個(gè)上界，但并不是上確界，但人們在表示的時(shí)候一般都習(xí)慣表示前者。

此外，一個(gè)問題本身也有它的復(fù)雜性，如果某個(gè)算法的復(fù)雜性到達(dá)了這個(gè)問題復(fù)雜性的下界，那就稱這樣的算法是最佳算法。

“大O記法”：在這種描述中使用的基本參數(shù)是 n，即問題實(shí)例的規(guī)模，把復(fù)雜性或運(yùn)行時(shí)間表達(dá)為n的函數(shù)。這里的“O”表示量級 (order)，比如說“二分檢索是** O(logn)**的”,也就是說它需要“通過logn量級的步驟去檢索一個(gè)規(guī)模為n的數(shù)組”記法 O ( f(n) )表示當(dāng) n增大時(shí)，運(yùn)行時(shí)間至多將以正比于 f(n)的速度增長。

這種漸進(jìn)估計(jì)對算法的理論分析和大致比較是非常有價(jià)值的，但在實(shí)踐中細(xì)節(jié)也可能造成差異。例如，一個(gè)低附加代價(jià)的O(n^2)算法在n較小的情況下可能比一個(gè)高附加代價(jià)的 O(nlogn)*算法運(yùn)行得更快。當(dāng)然，隨著n足夠大以后，具有較慢上升函數(shù)的算法必然工作得更快。

插入算法的復(fù)雜度分析

對給定規(guī)模的輸入，一個(gè)算法的運(yùn)行時(shí)間可能結(jié)果如下圖，對我們本次講解的插入算法，最佳情況是：T(n)=an+b；最差的結(jié)果是：T(n)=an^2+bn+c

對給定規(guī)模的輸入，一個(gè)算法的運(yùn)行時(shí)間可能結(jié)果

二、分治法

分治法的設(shè)計(jì)思想是：將一個(gè)難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個(gè)擊破，分而治之。

分治法定義

分治法的步驟

偽代碼

偽代碼

分治法分解之后合并所需要的算法的偽代碼

MERGE(A,p,q,r)

1  n1=q-p+1
2  n2=r-q
3  let L[1..n1+1] and R[1..n2+1] be new arrays
4  for i=1 to n1
5    L[i]=A[p+i-1]
6  for j=1 to n2
7    R[j]=A[q+j]
8  L[n1+1]=&
9  R[n2+1]=&
10  i=1
11  j=1
12  for k=p to r
13    if L[i]<=R[j]
14      A[k]=L[i]
15      i=i+1
16    else A[k]=R[j]
17      j=j+1

分治策略是：對于一個(gè)規(guī)模為n的問題，若該問題可以容易地解決（比如說規(guī)模n較小）則直接解決，否則將其分解為k個(gè)規(guī)模較小的子問題，這些子問題互相獨(dú)立且與原問題形式相同，遞歸地解這些子問題，然后將各子問題的解合并得到原問題的解。這種算法設(shè)計(jì)策略叫做分治法。

如果原問題可分割成k個(gè)子問題，1<k≤n，且這些子問題都可解并可利用這些子問題的解求出原問題的解，那么這種分治法就是可行的。由分治法產(chǎn)生的子問題往往是原問題的較小模式，這就為使用遞歸技術(shù)提供了方便。在這種情況下，反復(fù)應(yīng)用分治手段，可以使子問題與原問題類型一致而其規(guī)模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。這自然導(dǎo)致遞歸過程的產(chǎn)生。分治與遞歸像一對孿生兄弟，經(jīng)常同時(shí)應(yīng)用在算法設(shè)計(jì)之中，并由此產(chǎn)生許多高效算法。

核心思想如圖

圖解

定義整個(gè)分支法的偽代碼。進(jìn)行遞歸調(diào)用，知道最終每一個(gè)子序列都排列好，然后進(jìn)行MERGE合并。就好比是把一堆牌，分?jǐn)偝傻确值膬啥?，然后分成四堆，一直到最后，每一堆只剩下一張牌，不能再分。這時(shí)候就可以進(jìn)行合并，采用的偽代碼如上所述。

分治法

合并的過程

結(jié)束語

不得不說這個(gè)東西還真是厲害，也不愧是我學(xué)長說一個(gè)寒假也就看完一兩章的神書。這第一章具體的算法，就讓我花了整整半天時(shí)間去琢磨，現(xiàn)在腦子還是有點(diǎn)暈乎乎的。加油 繼續(xù)繼續(xù)~~~

個(gè)人宣言

知識傳遞力量，技術(shù)無國界，文化改變生活！