計(jì)算思維導(dǎo)論講義第4章-2014秋課件

第4章算法與復(fù)雜性4.1排序問(wèn)題及算法排序問(wèn)題基本排序算法PageRank排序4.2遞歸及遞歸算法遞歸遞歸算法4.3遺傳算法--計(jì)算復(fù)雜性與仿生學(xué)可求解與難求解問(wèn)題遺傳算法—一種仿生學(xué)算法的簡(jiǎn)單示例遺傳算法暨問(wèn)題求解算法的進(jìn)一步探討第4章算法與復(fù)雜性11.基本排序算法1）內(nèi)排序插入排序

基本思想：類似于打撲克牌時(shí)，一邊抓牌，一邊理牌的過(guò)程，每抓一張牌就把它插入到適當(dāng)?shù)奈恢?，牌抓完了，也理完了這種策略被稱為插入排序。第4章算法與復(fù)雜性24.1排序問(wèn)題及算法1.基本排序算法1）內(nèi)排序插入排序第4章算法與復(fù)雜性34.1排序問(wèn)題及算法1.基本排序算法1）內(nèi)排序插入排序第4章算法與復(fù)雜性44.1排序問(wèn)題及算法INSERTION-SORT(A)/*插入法-遞增排序1. fori=2toN2.{

key=A[i];/*key為待插入的未排序的數(shù)組元素，從第2個(gè)到第N個(gè)循環(huán)處理。對(duì)每個(gè)i,數(shù)組中A[1]到A[i-1]的元素已經(jīng)排好序,接著要使A[i]插入到適當(dāng)位置以使A[1]到A[i]排好序*/3. j=i-1;/*從排好序的最后一個(gè)元素開(kāi)始檢查*/4. While(j>0andA[j]>key)do5. { A[j+1]=A[j];6. j=j-1;}/*上面循環(huán)表示，如果A[j]>key,則要將已排序數(shù)組元素向后移動(dòng)，為key留出位置*/

7. A[j+1]=key;8.}/*算法結(jié)束*/ 1.基本排序算法1）內(nèi)排序簡(jiǎn)單選擇排序基本思想：一個(gè)輪次一個(gè)輪次的處理。首先在所有數(shù)組元素中找出最小值的元素，放在A[1]中；接著在不包含A[1]的余下的數(shù)組元素中再找出最小值的元素，放置在A[2]中；如此下去，一直到最后一個(gè)元素。這一排序策略被稱為簡(jiǎn)單選擇排序。第4章算法與復(fù)雜性54.1排序問(wèn)題及算法1.基本排序算法1）內(nèi)排序簡(jiǎn)單選擇排序第4章算法與復(fù)雜性74.1排序問(wèn)題及算法SELECTION-SORT(A)/*簡(jiǎn)單選擇法-遞增排序1. fori=1toN-1/*從第一個(gè)元素開(kāi)始處理，直到第N-1個(gè)元素。A[1]到A[i]的數(shù)組元素已經(jīng)排好序；下面的循環(huán)是將A[i]至A[N]的元素中最小值找出，放在A[i]中*/2.{

forj=i+1toN3. {ifA[j]<A[i]then/*使A[i+1]至A[N]中的每一個(gè)元素都與A[i]比較，若某一個(gè)A[j]比A[i]小，則交換A[i]和A[j]的值使A[i]始終為待排序數(shù)組元素中的最小值*/4. {temp=A[j];5. A[j]=A[i];6. A[j]=temp;7. }8. }9.}/*算法結(jié)束*/1.基本排序算法1）內(nèi)排序冒泡排序基本思想：也是一個(gè)輪次一個(gè)輪次的處理。在每一輪次中依次對(duì)待排序數(shù)組元素中相鄰的兩個(gè)元素進(jìn)行比較，將大的放前，小的放后--遞減排序(或者是將小的放前，大的放后--遞增排序)。第4章算法與復(fù)雜性84.1排序問(wèn)題及算法1.基本排序算法1）內(nèi)排序冒泡排序第4章算法與復(fù)雜性104.1排序問(wèn)題及算法BUBBLE-SORT(A)/*冒泡排序法-遞增排序1. fori=1toN-1/*從第一輪迭代，最多迭代N-1輪*/2.{

haschange=false;/*設(shè)置輪次中有無(wú)交換的一個(gè)標(biāo)志,如果其為false則表示無(wú)交換發(fā)生，為true則表示有交換發(fā)生*/

3. forj=1toN-i4. {ifA[j]>A[j+1]then/*每一輪都使A[j]與A[j+1]兩兩比較，若A[j]大，則交換A[j]與A[j+1]*/5. {temp=A[j];6. A[j]=A[j+1];7. A[j]=temp;8. haschange=true;9. }10. }11.if(haschange==false)thenbreak;/*如果本輪次沒(méi)有交換的情況發(fā)生，則終止循環(huán)，算法結(jié)束*/

12.}/*算法結(jié)束*/1.基本排序算法1）內(nèi)排序三個(gè)基本排序算法的比較第4章算法與復(fù)雜性114.1排序問(wèn)題及算法算法名稱時(shí)間復(fù)雜度空間復(fù)雜度穩(wěn)定性插入排序O(N2)O(1)穩(wěn)定簡(jiǎn)單選擇排序O(N2)O(1)不穩(wěn)定冒泡排序O(N2)O(1)穩(wěn)定2.基本排序算法1）內(nèi)排序快速排序基本思想：從待排序列中任取一個(gè)元素(例如取第一個(gè))作為中心，所有比它小的元素一律前放，所有比它大的元素一律后放，形成左右兩個(gè)子序列；然后再對(duì)各子序列重新選擇中心元素并依此規(guī)則調(diào)整，直到每個(gè)子序列的元素只剩一個(gè)，此時(shí)便為有序序列了。還有一些排序算法需要借助一些數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)，如桶排序、基數(shù)排序、堆排序等讀者可參閱有關(guān)書籍進(jìn)一步學(xué)習(xí)之。第4章算法與復(fù)雜性124.1排序問(wèn)題及算法2.基本排序算法2）外排序（Externalsorting）外排序環(huán)境：為充分利用存儲(chǔ)空間，操作系統(tǒng)將外存和內(nèi)存均劃分為若干相等大小的子空間，被稱為塊(Block)。由外存向內(nèi)存的數(shù)據(jù)移動(dòng)被稱為讀磁盤而由內(nèi)存向外存的數(shù)據(jù)移動(dòng)被稱為寫磁盤操作系統(tǒng)通常按塊讀寫磁盤并提供了相應(yīng)的讀磁盤函數(shù)簡(jiǎn)記為ReadBlock，和寫磁盤函數(shù)簡(jiǎn)記為WriteBlock。第4章算法與復(fù)雜性144.1排序問(wèn)題及算法第4章算法與復(fù)雜性15假設(shè)，一塊可以裝載Rblock個(gè)數(shù)據(jù)元素，待排序數(shù)據(jù)元素有Rproblem個(gè)，則其所占用的磁盤塊數(shù)約Bproblem=Rproblem/Rblock。圖中示意Rblock=5，Rproblem=60，Bproblem=12。假設(shè)內(nèi)存的塊數(shù)為Bmemory，圖中示意Bmemory=6。第4章算法與復(fù)雜性174.1排序問(wèn)題及算法9．{將第ith個(gè)位置的元素存入Moutput中的Poutput位置,Poutput指針按次序指向下一位置；10. If(Poutput指向結(jié)束位置)then11. {調(diào)用WriteBlock按次序?qū)output寫回磁盤；置Poutput為輸出內(nèi)存塊的起始位置；繼續(xù)進(jìn)行;}12．

獲取Mi的下一個(gè)元素.13. If(Mi有下一個(gè)元素)14. {

將Mi下一個(gè)元素存入Mcompare的第ith個(gè)位置。轉(zhuǎn)步驟7繼續(xù)執(zhí)行。}15. Else

{

調(diào)用readblock按次序讀Si的下一塊并存入Mi；16. If(Si有下一塊)17. {

將其第一個(gè)元素存入Mcompare的第ith個(gè)位置。轉(zhuǎn)步驟7繼續(xù)執(zhí)行。}18. ELSE{返回一個(gè)特殊值如Finished，以示Si子集合處理完畢，Mi為空，且使Mcompare中的第ith位置為該特殊值，表明該元素不參與Mcompare的比較操作。轉(zhuǎn)步驟7繼續(xù)執(zhí)行。}19.} 20.}/*若Mcompare的所有元素都是特殊值Finished，即沒(méi)有最小值，則算法結(jié)束*/2.基本排序算法3）PageRank排序—排序問(wèn)題的不同思考方法PageRank的基本概念PageRank是基于“從許多優(yōu)質(zhì)的網(wǎng)頁(yè)鏈接過(guò)來(lái)的網(wǎng)頁(yè)，必定還是優(yōu)質(zhì)網(wǎng)頁(yè)”這一基本想法來(lái)判定所有網(wǎng)頁(yè)的重要性，也是PageRank網(wǎng)頁(yè)排序算法的精髓。對(duì)網(wǎng)頁(yè)的鏈接，有兩種鏈接：正向鏈接和反向鏈接，對(duì)一個(gè)網(wǎng)頁(yè)而言，正向鏈接是該頁(yè)面指向其他頁(yè)面的鏈接，它將對(duì)指向頁(yè)面的重要度評(píng)價(jià)產(chǎn)生貢獻(xiàn)，反向鏈接是其他頁(yè)面指向該頁(yè)面的鏈接，將對(duì)本頁(yè)面的重要度評(píng)價(jià)產(chǎn)生貢獻(xiàn)。第4章算法與復(fù)雜性184.1排序問(wèn)題及算法2.基本排序算法3）PageRank排序—排序問(wèn)題的不同思考方法PageRank的基本概念簡(jiǎn)單處理，某個(gè)網(wǎng)頁(yè)的重要度指標(biāo)，即PageRank值，被平均地分配到其每一個(gè)正向鏈接上面，作為對(duì)其他網(wǎng)頁(yè)的貢獻(xiàn)度；而由反向鏈接獲得的貢獻(xiàn)度被加入到本網(wǎng)頁(yè)的重要度指標(biāo)上。如下圖所示第4章算法與復(fù)雜性194.1排序問(wèn)題及算法2.基本排序算法3）PageRank排序—排序問(wèn)題的不同思考方法PageRank算法及實(shí)例由問(wèn)題到數(shù)學(xué)的典型示例可將網(wǎng)頁(yè)超鏈接結(jié)構(gòu)抽象為矩陣，用線性代數(shù)方法進(jìn)行求解網(wǎng)頁(yè)數(shù)為N，則矩陣就為N×N的方陣，表達(dá)網(wǎng)頁(yè)i(行)與網(wǎng)頁(yè)j(列)的鏈接關(guān)系，矩陣的每個(gè)元素aij按如下方式取值。第4章算法與復(fù)雜性204.1排序問(wèn)題及算法2.基本排序算法3）PageRank排序—排序問(wèn)題的不同思考方法PageRank算法及實(shí)例由問(wèn)題到數(shù)學(xué)的典型示例轉(zhuǎn)移概率矩陣設(shè)上述鄰接矩陣記為A，將此鄰接矩陣轉(zhuǎn)置，記為AT。對(duì)AT進(jìn)行歸一化處理，即將AT的每個(gè)值除以其所在列的非零值的總個(gè)數(shù)，此即一概率形式，各列的概率之和為1。這樣形成的矩陣在PageRank被稱為“轉(zhuǎn)移概率矩陣”，各個(gè)行向量含有N個(gè)概率變量，表示狀態(tài)之間的轉(zhuǎn)移概率。第4章算法與復(fù)雜性214.1排序問(wèn)題及算法2.基本排序算法3）PageRank排序—排序問(wèn)題的不同思考方法PageRank算法及實(shí)例由問(wèn)題到數(shù)學(xué)的典型示例PageRank的計(jì)算就是求轉(zhuǎn)移概率矩陣最大特征值的特征向量網(wǎng)頁(yè)i的重要度為Ri，各網(wǎng)頁(yè)重要度的向量R，記為，即R=(R1,R2…,Rn)T，需要迭代計(jì)算，第j次迭代計(jì)算得到的R的結(jié)果記為R(j)。R的初始可設(shè)置為任意的值，記為R(0)=(R1(0),R2(0)…,Rn(0))T；按照轉(zhuǎn)移概率計(jì)算一輪后，可得到R(1)=cMR(0)，再進(jìn)一步計(jì)算R(2)=cMR(1)

，依次計(jì)算下去，可以通過(guò)c值調(diào)整，使得R(n)=R(n-1)，即R的值不再隨迭代次數(shù)增加而發(fā)生變化，即R=cMR，此時(shí)的R被稱為特征向量，即為所求各網(wǎng)頁(yè)的PageRank。第4章算法與復(fù)雜性224.1排序問(wèn)題及算法2.基本排序算法3）PageRank排序—排序問(wèn)題的不同思考方法PageRank算法及實(shí)例由問(wèn)題到數(shù)學(xué)的典型示例簡(jiǎn)單例子識(shí)別其鄰接關(guān)系第4章算法與復(fù)雜性244.1排序問(wèn)題及算法鏈接源頁(yè)面ID鏈接目標(biāo)頁(yè)面

ID12,3,4,5,72131,242,3,551,3,4,661,5752.基本排序算法3）PageRank排序—排序問(wèn)題的不同思考方法PageRank算法及實(shí)例由問(wèn)題到數(shù)學(xué)的典型示例簡(jiǎn)單例子基于鄰接關(guān)系構(gòu)造鄰接矩陣

A第4章算法與復(fù)雜性254.1排序問(wèn)題及算法2.基本排序算法3）PageRank排序—排序問(wèn)題的不同思考方法PageRank算法及實(shí)例由問(wèn)題到數(shù)學(xué)的典型示例簡(jiǎn)單例子計(jì)算表示PageRank的向量R(各個(gè)頁(yè)面的等級(jí)數(shù)構(gòu)成的向量)，存在著R=cMR的關(guān)系(c為定量)。為求R，可對(duì)矩陣M作特征值分解第4章算法與復(fù)雜性274.1排序問(wèn)題及算法2.基本排序算法3）PageRank排序—排序問(wèn)題的不同思考方法PageRank算法及實(shí)例由問(wèn)題到數(shù)學(xué)的典型示例簡(jiǎn)單例子分析PageRank的名次和反向鏈接的數(shù)目是基本一致的第4章算法與復(fù)雜性284.1排序問(wèn)題及算法2.基本排序算法3）PageRank排序—排序問(wèn)題的不同思考方法PageRank算法及實(shí)例由問(wèn)題到數(shù)學(xué)的典型示例簡(jiǎn)單例子分析第4章算法與復(fù)雜性294.1排序問(wèn)題及算法2.PageRank排序PageRank的概念示意圖