《算法設計與分析王紅梅第5章_減治法》由會員分享，可在線閱讀，更多相關《算法設計與分析王紅梅第5章_減治法（27頁珍藏版）》請在裝配圖網上搜索。
1、單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,算法設計與分析,清華大學出版社,算法設計與分析,清華大學出版社,單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,算法設計與分析,清華大學出版社,單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,算法設計與分析,清華大學出版社,單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,算法設計與分析,清華大學出版社,單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,
2、算法設計與分析,清華大學出版社,單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,算法設計與分析,清華大學出版社,單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,算法設計與分析,清華大學出版社,單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,算法設計與分析,清華大學出版社,單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,算法設計與分析,清華大學出版社,單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,
3、算法設計與分析,清華大學出版社,單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,算法設計與分析,清華大學出版社,單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,算法設計與分析,清華大學出版社,單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,算法設計與分析,清華大學出版社,算法設計與分析,清華大學出版社,單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,
4、算法設計與分析,清華大學出版社,單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,算法設計與分析,清華大學出版社,單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,算法設計與分析,清華大學出版社,單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,算法設計與分析,清華大學出版社,單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,算法設計與分析,清華大學出版社,單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,
5、算法設計與分析,清華大學出版社,單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,算法設計與分析,清華大學出版社,單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,算法設計與分析,清華大學出版社,單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,算法設計與分析,清華大學出版社,單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,算法設計與分析,清華大學出版社,單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,
6、算法設計與分析,清華大學出版社,單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,算法設計與分析,清華大學出版社,單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,5.1,減治法的設計思想,規(guī)模為,n,的原問題的解與較小規(guī)模（通常是,n,/2,）的子問題的解之間具有關系：,（,1,）原問題的解只存在于其中一個較小規(guī)模的子問題中；,（,2,）原問題的解與其中一個較小規(guī)模的解之間存在某種對應關系。,由于原問題的解與較小規(guī)模的子問題的解之間存在這種關系，所以，只需求解其中一個較小規(guī)模的子問題就可以得到原問題的解。,第,5,章
7、 減治法,子問題,的規(guī)模是,n,/2,子問題的解,原問題的解,原問題,的規(guī)模是,n,減治法的設計思想,基本思想：在有序表中，取中間記錄作為比較對象，若給定值與中間記錄的關鍵碼相等，則查找成功；若給定值小于中間記錄的關鍵碼，則在中間記錄的左半區(qū)繼續(xù)查找；若給定值大于中間記錄的關鍵碼，則在中間記錄的右半區(qū)繼續(xù)查找。不斷重復上述過程，直到查找成功，或所查找的區(qū)域無記錄，查找失敗。,5.2.1,折半查找,r,1,r,mid,-,1,r,mid,r,mid,+1,r,n,（,mid,=,(,1+,n,),/2,）,如果,k,r,mid,查找這里,k,5.2,查找問題中的減治法,例：查找值為,14,的記錄
8、的過程：,0 1 2 3 4 5 6 7 8 9 10 11 12 13,7 14 18 21 23 29 31 35 38 42 46 49 52,low=1,high=13,mid=7,high=6,mid=3,high=2,mid=1,3114,1814,714,low=2,mid=2,14=14,算法,5.1,折半查找,1.low=1,；,high=n,；,/,設置初始查找區(qū)間,2.,測試查找區(qū)間,low,，,high,是否存在，若不存在，則查找失?。?否則,3.,取中間點,mid=,(,low+high,),/2;,比較,k,與,rmid,，有以下三種情況：,3.1,若,krmid,
9、，則,low=mid+1,；查找在右半區(qū)進行，轉,2,；,3.3,若,k=rmid,，則查找成功，返回記錄在表中位置,mid,；,偽代碼,判定樹,描述折半查找的判定過程。,長度為,n,的判定樹的構造方法為：,（,1,）當,n,=0,時，判定樹為空；,（,2,）當,n,0,時，判定樹的根結點是有序表中序號為,mid=(n+1)/2,的記錄，根結點的左子樹是與有序表,r1 rmid-1,相對應的判定樹，根結點的右子樹是與,rmid+1 rn,相對應的判定樹。,具有,11,個結點的判定樹,6,3,1,2,5,4,8,11,10,7,9,在表中查找任一記錄的過程，即是判定樹中從根結點到該記錄結點的路徑
10、，和給定值的比較次數等于該記錄結點在樹中的層數。具有,n,個結點的判定數的深度為 。,5.3.1,插入排序,插入排序是減治法的減一技術。,5.3,排序問題中的減治法,插入排序基本思想：依次將待排序序列中的每一個記錄插入到一個已經排好序的序列中，直到全部記錄都排好序,當插入第,i,個對象時，前面的,R1,R2,Ri-1,已經排好序，此時，用,Ri,的關鍵字與,Ri-1,Ri-2,的關鍵字順序進行比較，找到插入位置即將,Ri,插入，原來位置上對象向后順移。,直接插入排序舉例,i (1)(2)(3)(4)(5)(6)(0),21,25 49 25*16 08 25,1 ,21 25,49 25*16
11、 08 49,2 ,21 25 49,25*16 08 25*,3 ,21 25 25*49,16 08 16,4 ,16 21 25 25*49,08 08,5 ,08 16 21 25 25*49,直接插入排序算法,INSERTSORT(rectype R),int i,j;,for(i=2;in;i+),R0,Ri;,j,i-1;,while(R0.keyRj.key),Rj+1,Rj-;,Rj+1,R0;,算法分析,直接插入排序算法由兩重循環(huán)組成，對于有,n,個記錄的排序，內循環(huán)表明完成一趟排序所需進行的記錄關鍵字間的比較和記錄的后移。,若初始時關鍵字遞增有序（正序），這是最好情況。每
12、一趟排序中僅需進行一次關鍵字的比較，所以總的比較次數為,n-1,。在,while,循環(huán)之前和之中，至少要移動記錄兩次，所以總的移動次數為,2(n-1),。,若初始時關鍵字遞減有序（反序），這是最壞情況。這時的記錄比較和移動次數分別為：,5.3.2,堆排序,以結點的編號作為下標，將堆用順序存儲結構（即數組）來存儲，則堆對應于一組序列。,(a),大根堆及其對應的序列,(b),小根堆及其對應的序列,47 35 26 20 18 7 13 10,7 10 13 18 35 26 47 20,47,35,26,13,18,20,7,10,26,10,13,47,35,18,7,20,堆排序的基本思想是：
13、首先將待排序的記錄序列構造成一個堆，此時，選出了堆中所有記錄的最大者即堆頂記錄，然后將它從堆中移走（通常將堆頂記錄和堆中最后一個記錄交換），并將剩余的記錄再調整成堆，這樣又找出了次大的記錄，以此類推，直到堆中只有一個記錄為止。,r,1,r,2,r,i,r,i,+1,r,n,-,1,r,n,無序區(qū) 有序區(qū),為一個堆 已經位于最終位置,堆頂和堆中最后,一個記錄交換,堆調整問題,：將一個無序序列調整為堆,（,1,）篩選法調整堆,關鍵問題：完全二叉樹中，根結點的左右子樹均是堆，如何調整根結點，使整個完全二叉樹成為一個堆？,(,a)28,與,35,交換,(b)28,與,32,交換,(c),將,28,篩到
14、葉子,28,32,18,20,12,18,20,12,35,32,18,20,12,35,35,28,32,28,假設當前要篩選結點的編號為,k,，堆中最后一個結點的編號為,n,，并且結點,k,的左右子樹均是堆（即,rk+1 rn,滿足堆的條件），則篩選算法用偽代碼可描述為：,算法,5.3,篩選法調整堆,1.,設置,i,和,j,，分別指向當前要篩選的結點和要篩選結點的左孩子；,2.,若結點,i,已是葉子，則篩選完畢；否則，比較要篩選結點的左右 孩子結點，并將,j,指向關鍵碼較大的結點；,3.,將要篩選結點,i,的關鍵碼與結點,j,的關鍵碼進行比較，有以下兩種情況：,3.1,如果結點,i,的關鍵
15、碼大，則完全二叉樹已經是堆；,3.2,否則將,ri,與,rj,交換；令,i=j,，轉步驟,2,繼續(xù)進行篩選；,偽代碼,時間性能是,O,(log,2,n,),。,算法,5.4,篩選法調整堆,void SiftHeap,(,int r,int k,int n,),i=k;j=2*i;/,置,i,為要篩的結點，,j,為,i,的左孩子,while,(,j=n,),/,篩選還沒有進行到葉子,if,(,jn&rjrj,),/,根結點已經大于左右孩子中的較大者,break;,else,rirj;/,將根結點與結點,j,交換,i=j;j=2*i;/,被篩結點位于原來結點,j,的位置,C+,描述,32,18,2
16、0,12,40,35,8,28,20,32,18,20,12,40,8,20,35,28,18,20,12,40,8,20,35,28,32,(a)35,與,28,交換,(b)35,與,32,交換,(c)3540,調整完畢,（,2,）插入法調整堆,關鍵問題是：在堆中插入一個結點，如何調整被插入結點，使整個完全二叉樹仍然是一個堆？,假設當前堆中有,k,個結點，則要插入結點的編號為,k+1,，插入法調整堆的算法如下：,算法,5.5,插入法調整堆,1.,設,i,指向當前要插入的結點；,2.,若結點,i,是整個堆的根結點，則調整完畢；,3,否則，設,j,指向結點,i,的雙親結點；將結點,i,與結點,j,進行比較；,3.1,如果結點,i,的關鍵碼小，則完全二叉樹已經是堆，調整完畢；,3.2,否則將,ri,與,rj,交換；令,i=j,，轉步驟,2,繼續(xù)進行調整；,偽代碼,時間復雜性為,O,(log,2,n,),。,算法,5.6,插入法調整堆,void InsertHeap,(,int r,int k,),/,堆中有,k,個結點，現插入一個新結點,k+1,i=k+1;/,置,i,為要插入的結點,wh
算法設計與分析王紅梅第5章_減治法
