開篇語

今天開始看《算法導(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)購(gòu)算法導(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ù)放到高序號(hào)，然后再次對(duì)更加之前的數(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è)上界担租，但并不是上確界砸民，但人們?cè)诒硎镜臅r(shí)候一般都習(xí)慣表示前者。

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

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

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

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

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

對(duì)給定規(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

分治策略是：對(duì)于一個(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)生钟病。分治與遞歸像一對(duì)孿生兄弟萧恕，經(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é)長(zhǎng)說一個(gè)寒假也就看完一兩章的神書。這第一章具體的算法肆糕，就讓我花了整整半天時(shí)間去琢磨般堆，現(xiàn)在腦子還是有點(diǎn)暈乎乎的。加油 繼續(xù)繼續(xù)~~~

個(gè)人宣言

知識(shí)傳遞力量诚啃，技術(shù)無國(guó)界淮摔，文化改變生活！