算法設(shè)計(jì)與分析-變治法

1、1 首先是首先是”變變“， 將問(wèn)題的實(shí)例將問(wèn)題的實(shí)例變形，變形，變得更容易求解；變得更容易求解； 思考：和思考：和分治分治與與減治減治的區(qū)別的區(qū)別 然后是然后是”治治“，對(duì)問(wèn)題的實(shí)例進(jìn)行求解。，對(duì)問(wèn)題的實(shí)例進(jìn)行求解。 變治法有三個(gè)變形變治法有三個(gè)變形: （1）實(shí)例化簡(jiǎn)）實(shí)例化簡(jiǎn)同樣問(wèn)題同樣問(wèn)題 （2）改變表現(xiàn)）改變表現(xiàn)同樣實(shí)例同樣實(shí)例 （3）問(wèn)題化簡(jiǎn)）問(wèn)題化簡(jiǎn)另一問(wèn)題另一問(wèn)題2 （1）實(shí)例化簡(jiǎn)）實(shí)例化簡(jiǎn)同樣問(wèn)題同樣問(wèn)題 6.1 預(yù)排序預(yù)排序 6.2 高斯消去法高斯消去法 6.3 平衡查找樹平衡查找樹AVL樹樹（2）改變表現(xiàn)）改變表現(xiàn)同樣實(shí)例同樣實(shí)例 6.3 2-3樹樹 6.4 堆和堆排序堆和堆

2、排序 6.5 霍納法則和二進(jìn)制冪霍納法則和二進(jìn)制冪（3）問(wèn)題化簡(jiǎn)）問(wèn)題化簡(jiǎn)另一問(wèn)題另一問(wèn)題 6.63 列表是列表是有序有序的話，許多關(guān)于列表的問(wèn)題更容易求解。的話，許多關(guān)于列表的問(wèn)題更容易求解。 因此很多問(wèn)題需要因此很多問(wèn)題需要先排序先排序，則該問(wèn)題的時(shí)間效率依賴，則該問(wèn)題的時(shí)間效率依賴于排序算法的效率。于排序算法的效率。 回憶前面所學(xué)的排序算法：回憶前面所學(xué)的排序算法： 插入排序最差插入排序最差(n2) 平均平均 (n2) 最優(yōu)最優(yōu) (n) 快速排序最差快速排序最差(n2) 平均平均(1.38nlog2n) 最優(yōu)最優(yōu)(nlog2n) 合并排序最差合并排序最差(nlog2n)選擇排序選擇排序(

3、n2)冒泡排序冒泡排序(n2)4 例例1、檢驗(yàn)數(shù)組中元素的唯一性、檢驗(yàn)數(shù)組中元素的唯一性 蠻力法如何做？時(shí)間效率是多少？蠻力法如何做？時(shí)間效率是多少？如果先排序，則如何檢查元素的唯一性？如果先排序，則如何檢查元素的唯一性？只需檢查相互緊挨的元素。只需檢查相互緊挨的元素。PresortElementUniqueness(A0.n-1) /先對(duì)數(shù)組排序再驗(yàn)證唯一性先對(duì)數(shù)組排序再驗(yàn)證唯一性 /輸入：數(shù)組輸入：數(shù)組A /輸出：若輸出：若A沒(méi)有相等的元素，返回沒(méi)有相等的元素，返回“true”,否則返回否則返回“false”. 對(duì)數(shù)組排序；對(duì)數(shù)組排序； for i=0 to n-2 do if Ai=Ai

4、+1 return false return true整個(gè)過(guò)程整個(gè)過(guò)程時(shí)間效率時(shí)間效率是多少？是多少？5 例例2、模式計(jì)算、模式計(jì)算 模式：模式：指數(shù)組列表中指數(shù)組列表中出現(xiàn)次數(shù)出現(xiàn)次數(shù)最多的最多的值值。 如如5,1,5,7,6,5,7中中5是模式是模式 所能想到的求模式的方法：所能想到的求模式的方法：用輔助列表列出所有元素及其出現(xiàn)頻率。用輔助列表列出所有元素及其出現(xiàn)頻率。時(shí)間效率如何分析？時(shí)間效率如何分析？采用排序的思想采用排序的思想先排序后計(jì)算相鄰接次數(shù)最多的等值元素。先排序后計(jì)算相鄰接次數(shù)最多的等值元素。時(shí)間效率如何分析？時(shí)間效率如何分析？6 思考：預(yù)排序還可以用在什么方面？思考：預(yù)排序

5、還可以用在什么方面？ 查找查找 分析順序查找和先排序再查找的時(shí)間效率分析順序查找和先排序再查找的時(shí)間效率 如果要在同一個(gè)列表中進(jìn)行多次查找，在排序上如果要在同一個(gè)列表中進(jìn)行多次查找，在排序上花費(fèi)時(shí)間是值得的。花費(fèi)時(shí)間是值得的。 課堂練習(xí)：課堂練習(xí)： 采用合并排序?yàn)轭A(yù)排序，折半查找，要做多少次采用合并排序?yàn)轭A(yù)排序，折半查找，要做多少次查找才能使得對(duì)一個(gè)由查找才能使得對(duì)一個(gè)由n個(gè)元素構(gòu)成的數(shù)組所做個(gè)元素構(gòu)成的數(shù)組所做的預(yù)排序是有意義的。的預(yù)排序是有意義的。7 預(yù)排序的其他應(yīng)用：預(yù)排序的其他應(yīng)用： 對(duì)點(diǎn)排序，拓?fù)渑判驅(qū)c(diǎn)排序，拓?fù)渑判?課堂練習(xí)：課堂練習(xí)： P153 4 8 科學(xué)計(jì)算中通常需要解多個(gè)

6、變量的方程組，這些方程組科學(xué)計(jì)算中通常需要解多個(gè)變量的方程組，這些方程組當(dāng)中最簡(jiǎn)單的是線性方程組，也就是變量的次數(shù)均為當(dāng)中最簡(jiǎn)單的是線性方程組，也就是變量的次數(shù)均為1次的。次的。 求解線性方程的方法求解線性方程的方法 有利用高斯有利用高斯消元消元的直接法以及的直接法以及迭代法迭代法。體現(xiàn)的變治的思想：體現(xiàn)的變治的思想： 將方程組變成一個(gè)具有特殊性質(zhì)的方程組將方程組變成一個(gè)具有特殊性質(zhì)的方程組(上三角矩陣上三角矩陣)9 一般的線性方程組是指如下形式的方程組：一般的線性方程組是指如下形式的方程組：11 112 21121 122 2221 12 2n nn nmmmn nma xa xa xba

7、xa xa xba xa xa xb 1011121111212122222212000nnnnnnnnnnaaaaaaaaaaaaaaa 分消元過(guò)程和回代過(guò)程。消元過(guò)程將原方程組變分消元過(guò)程和回代過(guò)程。消元過(guò)程將原方程組變?yōu)樯先欠匠探M，回代過(guò)程得到方程組的解。為上三角方程組，回代過(guò)程得到方程組的解。1105412321321321xxxxxxxxx 2200333011120333011120111511411122/ 232121232/ 13122rrrrrr1 0 1 123xxx，回代后得12 GaussElimination(A1.n, b1.n) / 輸入：系數(shù)矩陣輸入：系數(shù)矩

8、陣A及常數(shù)項(xiàng)及常數(shù)項(xiàng) b / 輸出：方程組的增廣矩陣等價(jià)的上三角矩陣輸出：方程組的增廣矩陣等價(jià)的上三角矩陣 for i=1 to n do Ain+1 =bi for i =1 to n-1 do for j= i+1 to n do for k = i to n+1 do Ajk = Ajk Aik*Aji/Aii13 高斯消元法的效率分析高斯消元法的效率分析 基本操作：乘法基本操作：乘法 執(zhí)行次數(shù)：易見，三重循環(huán)執(zhí)行次數(shù)：易見，三重循環(huán) C(n)(n3)14高斯消去法的高斯消去法的現(xiàn)代商業(yè)實(shí)現(xiàn)現(xiàn)代商業(yè)實(shí)現(xiàn)是以是以LU分解為基礎(chǔ)分解為基礎(chǔ)的。的。15 05412321321321xxxxxx

9、xxx111114112A12121012001L200330112U系數(shù)矩陣為系數(shù)矩陣為下三角矩陣下三角矩陣L，由主對(duì)角線上的，由主對(duì)角線上的1以及在高斯消去過(guò)程中行的乘數(shù)構(gòu)成以及在高斯消去過(guò)程中行的乘數(shù)構(gòu)成上三角矩陣上三角矩陣U是消去的結(jié)果是消去的結(jié)果可觀察出可觀察出兩個(gè)矩陣兩個(gè)矩陣的乘積的乘積LU等于等于A16記原方程組為記原方程組為 A X =b A=LU 則原方程組為則原方程組為L(zhǎng)UX=b其求解轉(zhuǎn)化為兩個(gè)三角形方程組的求解：其求解轉(zhuǎn)化為兩個(gè)三角形方程組的求解： LY=b 下三角方程組下三角方程組 UX=Y 上三角方程組上三角方程組1705 21 3221121211yyyyyy22

10、333 1 2332321xxxxxx與與LY=b, UX=Y對(duì)應(yīng)的方程組如下：對(duì)應(yīng)的方程組如下：易得：易得： (y1,y2,y3)=(1,3,-2), (x1,x2,x3)=(1,0,-1)18 1 一旦的到矩陣一旦的到矩陣A的的LU分解，無(wú)論對(duì)于什么樣的分解，無(wú)論對(duì)于什么樣的右邊向量右邊向量b，我們都可以對(duì)方程組，我們都可以對(duì)方程組Ax=b求解，每求解，每次求一個(gè)。次求一個(gè)。 2 LU分解不需要額外的存儲(chǔ)空間分解不需要額外的存儲(chǔ)空間19111211112121222212221212100010001nnnnnnnnnnnnaaaxxxaaaxxxaaaxxx 逆矩陣的定義：求矩陣求矩陣

11、A 的逆矩陣，如何轉(zhuǎn)換的逆矩陣，如何轉(zhuǎn)換20求矩陣求矩陣 A 的逆矩陣，轉(zhuǎn)化為求解的逆矩陣，轉(zhuǎn)化為求解n個(gè)方程組個(gè)方程組 A Xj =bj 其中，其中， bj是單位矩陣是單位矩陣的第的第j列，而列，而Xj 則是逆矩陣的第則是逆矩陣的第j列。列。10001000121n階矩陣的行列式的計(jì)算由遞歸公式定義：階矩陣的行列式的計(jì)算由遞歸公式定義： 其中，其中， n=1時(shí)，時(shí)，det A=a11，若，若j為奇數(shù)，為奇數(shù)，sj=1， 若若j為偶數(shù)，為偶數(shù)，sj=-1例如例如n=3的情形如下：的情形如下：11121322232123212221222311121332333133313231323311 2

12、2 3312 23 3121 32 1331 22 1321 12 3332 23 11aaaaaaaaaaaaaaaaaaaaaaaaaa aa a aa a aa a aa a aa a anjjjAsA1detdet22 按照定義計(jì)算高階行列式是不可能的。按照定義計(jì)算高階行列式是不可能的。 可利用高斯消元法：可利用高斯消元法： 矩陣矩陣A的行列式的行列式=消元后上三角矩陣的行列式消元后上三角矩陣的行列式 =對(duì)角線上元素之乘積。對(duì)角線上元素之乘積。例如，上式中例如，上式中 det A=2 3 2=1220033011211111411223 課堂練習(xí)：課堂練習(xí)： 考慮高斯消去法的反向替換的

13、運(yùn)行時(shí)間效率類型考慮高斯消去法的反向替換的運(yùn)行時(shí)間效率類型是多少？是多少？24二叉查找樹是一種重要的數(shù)據(jù)結(jié)構(gòu)二叉查找樹是一種重要的數(shù)據(jù)結(jié)構(gòu)看書看書p162-163，思考下列問(wèn)題：，思考下列問(wèn)題：1 二叉查找樹的特點(diǎn)是？二叉查找樹的特點(diǎn)是？2 在平均情況下，查找，插入，刪除的效率是？在平均情況下，查找，插入，刪除的效率是？3 最差情況是一種什么情況？最差情況是一種什么情況？4 最差情況效率是多少？最差情況效率是多少？25把一個(gè)集合變換成一棵二叉查找樹是把一個(gè)集合變換成一棵二叉查找樹是改變表現(xiàn)技改變表現(xiàn)技術(shù)術(shù)的一個(gè)實(shí)例的一個(gè)實(shí)例好處是：好處是：在平均情況下，查找，插入，刪除的效率是在平均情況下，查

14、找，插入，刪除的效率是(logn)最差情況下，最差情況下， (n)，退化成線性的情況，退化成線性的情況26 考慮一種既能夠保留經(jīng)典二叉查找樹的好特性考慮一種既能夠保留經(jīng)典二叉查找樹的好特性 又能夠避免它退化到最差情況的數(shù)據(jù)結(jié)構(gòu)又能夠避免它退化到最差情況的數(shù)據(jù)結(jié)構(gòu) 兩種方法：兩種方法： 實(shí)例化簡(jiǎn)：實(shí)例化簡(jiǎn)：不平衡二叉查找樹變?yōu)槠胶獾男问讲黄胶舛娌檎覙渥優(yōu)槠胶獾男问?改變表現(xiàn)：改變表現(xiàn)：允許一棵查找樹的單個(gè)節(jié)點(diǎn)中不止包允許一棵查找樹的單個(gè)節(jié)點(diǎn)中不止包含一個(gè)元素。含一個(gè)元素。27 看書看書p163,p166回憶及思考下面問(wèn)題回憶及思考下面問(wèn)題 1 AVL樹的概念樹的概念 2 AVL樹查找效率與什么

15、相關(guān)？樹查找效率與什么相關(guān)？ 3 最差情況最差情況28 n個(gè)節(jié)點(diǎn)的個(gè)節(jié)點(diǎn)的AVL樹的高度樹的高度h 對(duì)于隨機(jī)鍵的列表構(gòu)造的對(duì)于隨機(jī)鍵的列表構(gòu)造的AVL樹，得到它的平均高度的樹，得到它的平均高度的精確公式被證明是有難度的。精確公式被證明是有難度的。 實(shí)驗(yàn)表明，這個(gè)高度大約是實(shí)驗(yàn)表明，這個(gè)高度大約是1.01log2n+0.1 在平均情況下，查找一棵在平均情況下，查找一棵AVL樹需要的比較次數(shù)和用折樹需要的比較次數(shù)和用折半查找一個(gè)有序數(shù)組是幾乎相同的。半查找一個(gè)有序數(shù)組是幾乎相同的。 在最差情況下查找和插入的效率屬于在最差情況下查找和插入的效率屬于(logn) 缺點(diǎn)：缺點(diǎn)： 頻繁的旋轉(zhuǎn)，維護(hù)平衡以及

16、總體上的復(fù)雜性頻繁的旋轉(zhuǎn)，維護(hù)平衡以及總體上的復(fù)雜性3277. 1)2(log4405. 1log22nhn29 2-3樹是一種樹是一種特殊特殊的高度平衡樹，允許結(jié)點(diǎn)的高度平衡樹，允許結(jié)點(diǎn)最多最多包含包含兩兩個(gè)個(gè)關(guān)鍵字。兩類結(jié)點(diǎn)：關(guān)鍵字。兩類結(jié)點(diǎn)：2-node、3-node。樹中所有葉子必須位于樹中所有葉子必須位于同一層同一層。k k k2k1,k22-node3-node30 看書理解看書理解 1 搜索算法搜索算法p167 2 插入算法插入算法p16831 搜索算法搜索算法 如果待搜索樹的根是如果待搜索樹的根是2-node型結(jié)點(diǎn)，搜索操作型結(jié)點(diǎn)，搜索操作與二叉搜索樹搜索操作相同；與二叉搜索樹

17、搜索操作相同； 如果待搜索樹的根是如果待搜索樹的根是3-node型結(jié)點(diǎn)，最多只需型結(jié)點(diǎn)，最多只需要比較兩次就可以知道是搜索成功還是需要向要比較兩次就可以知道是搜索成功還是需要向3棵子樹繼續(xù)遞歸搜索?？米訕淅^續(xù)遞歸搜索。32 插入算法：插入算法： 當(dāng)一個(gè)結(jié)點(diǎn)當(dāng)一個(gè)結(jié)點(diǎn)x需要插入到需要插入到2-3樹中的時(shí)候，總是根據(jù)它樹中的時(shí)候，總是根據(jù)它的大小關(guān)系，把其插入到葉結(jié)點(diǎn)中。的大小關(guān)系，把其插入到葉結(jié)點(diǎn)中。 插入前首先調(diào)用搜索算法找到待插入的葉結(jié)點(diǎn)，如插入前首先調(diào)用搜索算法找到待插入的葉結(jié)點(diǎn)，如果該葉結(jié)點(diǎn)是果該葉結(jié)點(diǎn)是2-node型的，則直接插入即可；型的，則直接插入即可； 如果該葉結(jié)點(diǎn)是如果該葉結(jié)點(diǎn)

18、是3-node型的，在按序插入到葉結(jié)點(diǎn)后，型的，在按序插入到葉結(jié)點(diǎn)后，需要把葉結(jié)點(diǎn)拆分（因?yàn)椴迦牒笫沟萌~結(jié)點(diǎn)的關(guān)鍵需要把葉結(jié)點(diǎn)拆分（因?yàn)椴迦牒笫沟萌~結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)為字個(gè)數(shù)為3，不滿足，不滿足2-3樹的要求）。樹的要求）。 拆分過(guò)程首先在三個(gè)關(guān)鍵字挑選值在中間的關(guān)鍵字，拆分過(guò)程首先在三個(gè)關(guān)鍵字挑選值在中間的關(guān)鍵字，提到上一層，或者作為新結(jié)點(diǎn)，或者插入原來(lái)的內(nèi)提到上一層，或者作為新結(jié)點(diǎn)，或者插入原來(lái)的內(nèi)結(jié)點(diǎn)中；關(guān)鍵字最小的作為左子樹，關(guān)鍵字最大的結(jié)點(diǎn)中；關(guān)鍵字最小的作為左子樹，關(guān)鍵字最大的作為右子樹。如果內(nèi)結(jié)點(diǎn)的插入導(dǎo)致結(jié)點(diǎn)過(guò)大，按作為右子樹。如果內(nèi)結(jié)點(diǎn)的插入導(dǎo)致結(jié)點(diǎn)過(guò)大，按照上述規(guī)則繼續(xù)拆分。

19、照上述規(guī)則繼續(xù)拆分。33 操作效率與什么相關(guān)？操作效率與什么相關(guān)？ 樹高樹高h(yuǎn) 若有若有n個(gè)關(guān)鍵字，構(gòu)成一棵全部由個(gè)關(guān)鍵字，構(gòu)成一棵全部由2節(jié)點(diǎn)構(gòu)成的滿樹，節(jié)點(diǎn)構(gòu)成的滿樹，n與與h之間之間的關(guān)系為？的關(guān)系為？ 若有若有n個(gè)關(guān)鍵字，構(gòu)成一棵全部由個(gè)關(guān)鍵字，構(gòu)成一棵全部由3節(jié)點(diǎn)構(gòu)成的滿樹，節(jié)點(diǎn)構(gòu)成的滿樹，n與與h之間之間的關(guān)系為？的關(guān)系為？ 所以高度的范圍是：所以高度的范圍是： 無(wú)論在最差還是平均，查找，插入和刪除時(shí)間效率都是對(duì)數(shù)類型無(wú)論在最差還是平均，查找，插入和刪除時(shí)間效率都是對(duì)數(shù)類型1=124221hhn1) 1(log1) 1(log23nhn1=2 1 2 3 .2 32(1 3 . 3

20、 )31hhhn 34 看書看書p170-p173回憶及理解回憶及理解 1 堆的定義堆的定義 2 堆的構(gòu)建方法堆的構(gòu)建方法 3 自底向上構(gòu)造法的時(shí)間效率自底向上構(gòu)造法的時(shí)間效率 4 自頂向下構(gòu)造法的時(shí)間效率自頂向下構(gòu)造法的時(shí)間效率 5 堆中刪除元素的算法堆中刪除元素的算法35 1 堆的定義堆的定義 堆是一棵二叉樹，樹中節(jié)點(diǎn)包含鍵，滿足下堆是一棵二叉樹，樹中節(jié)點(diǎn)包含鍵，滿足下面兩個(gè)條件：面兩個(gè)條件： 樹的形狀：二叉樹樹的形狀：二叉樹 父母：每個(gè)節(jié)點(diǎn)的鍵都要大于或等于它子女父母：每個(gè)節(jié)點(diǎn)的鍵都要大于或等于它子女的鍵。的鍵。36首先把數(shù)組按序填充到堆中各個(gè)結(jié)點(diǎn)首先把數(shù)組按序填充到堆中各個(gè)結(jié)點(diǎn)然后按照

21、自下而上，從右至左的順序，從最后的父然后按照自下而上，從右至左的順序，從最后的父母節(jié)點(diǎn)開始，到根為止，檢查這些節(jié)點(diǎn)的值是否母節(jié)點(diǎn)開始，到根為止，檢查這些節(jié)點(diǎn)的值是否都滿足子結(jié)點(diǎn)比父結(jié)點(diǎn)小的約束條件。都滿足子結(jié)點(diǎn)比父結(jié)點(diǎn)小的約束條件。如果不滿足則調(diào)換父子結(jié)點(diǎn)的位置，然后再檢查在如果不滿足則調(diào)換父子結(jié)點(diǎn)的位置，然后再檢查在新的位置上，是不是滿足父母優(yōu)勢(shì)要求。新的位置上，是不是滿足父母優(yōu)勢(shì)要求。用自底向上法為用自底向上法為1，8，6，5，3，7，4構(gòu)造一個(gè)堆構(gòu)造一個(gè)堆37 最壞情況最壞情況 每個(gè)位于樹的第每個(gè)位于樹的第i層的鍵都會(huì)移動(dòng)到葉子層層的鍵都會(huì)移動(dòng)到葉子層h中中 移動(dòng)到下一層需要進(jìn)行幾次比較

22、？移動(dòng)到下一層需要進(jìn)行幾次比較？ 兩次。位于第兩次。位于第i層的鍵移到葉子層層的鍵移到葉子層h需要幾次比較？需要幾次比較？ 需要需要2(h-i)次鍵值比較。次鍵值比較。 因此有下式：因此有下式： 結(jié)論結(jié)論:一個(gè)規(guī)模為一個(gè)規(guī)模為n的堆只需不到的堆只需不到2n次比較就能構(gòu)造完次比較就能構(gòu)造完成成 10210i)1(log(22)(2)(2)(hiihiworstnnihihnC層的鍵第38 將包含新鍵將包含新鍵K附加在當(dāng)前堆的最后一個(gè)葉子后面附加在當(dāng)前堆的最后一個(gè)葉子后面 將新鍵和父母比較交換將新鍵和父母比較交換 這個(gè)鍵向上走，直到它不大于它的父母為止這個(gè)鍵向上走，直到它不大于它的父母為止用自頂向

23、下法為用自頂向下法為1，8，6，5，3，7，4構(gòu)造一個(gè)堆構(gòu)造一個(gè)堆 思考一個(gè)新鍵插入思考一個(gè)新鍵插入i個(gè)元素構(gòu)成的堆的比較次數(shù)個(gè)元素構(gòu)成的堆的比較次數(shù) N個(gè)規(guī)模問(wèn)題的比較次數(shù)個(gè)規(guī)模問(wèn)題的比較次數(shù)39 只考慮刪除根中的鍵只考慮刪除根中的鍵 把待刪除結(jié)點(diǎn)與堆中最后一個(gè)鍵把待刪除結(jié)點(diǎn)與堆中最后一個(gè)鍵K對(duì)調(diào)。對(duì)調(diào)。 執(zhí)行刪除操作并把堆的大小減一。執(zhí)行刪除操作并把堆的大小減一。 對(duì)刪除后的堆進(jìn)行調(diào)整直到滿足堆的約束條件。對(duì)刪除后的堆進(jìn)行調(diào)整直到滿足堆的約束條件。 刪除的效率分析：刪除的效率分析： 取決于交換和規(guī)模減一后，樹的取決于交換和規(guī)模減一后，樹的堆化堆化所需的鍵值所需的鍵值比較次數(shù)。比較次數(shù)。 因

24、為鍵值比較次數(shù)不可能超過(guò)堆的高度的兩倍，因?yàn)殒I值比較次數(shù)不可能超過(guò)堆的高度的兩倍，刪除的時(shí)間也是屬于對(duì)數(shù)類型的。刪除的時(shí)間也是屬于對(duì)數(shù)類型的。 40 堆排序主要包括兩個(gè)步驟：堆排序主要包括兩個(gè)步驟： (1)對(duì)于給定的數(shù)組構(gòu)造相應(yīng)的堆。對(duì)于給定的數(shù)組構(gòu)造相應(yīng)的堆。 (2)對(duì)所構(gòu)造的堆執(zhí)行對(duì)所構(gòu)造的堆執(zhí)行n-1次刪除堆的根結(jié)點(diǎn)的操次刪除堆的根結(jié)點(diǎn)的操作，把刪除得到的結(jié)點(diǎn)保存在給定數(shù)組中。作，把刪除得到的結(jié)點(diǎn)保存在給定數(shù)組中。 41 用堆排序?qū)?shù)組用堆排序?qū)?shù)組2，9，7，6，5，8排序排序 步驟步驟1：構(gòu)造堆：構(gòu)造堆 2,9,7,6,5,8 2,9,8,6,5,7 2,9,8,6,5,7 9,2,

25、8,6,5,7 9,6,8,2,5,742 步驟步驟2：刪除根結(jié)點(diǎn)：刪除根結(jié)點(diǎn) 9,6,8,2,5,7 7,6,8,2,5 8,6,7,2,5 5,6,7,2 7,6,5,2 2,6,5 6,5,2 5,2 2 43 1 構(gòu)造堆的效率是多少？構(gòu)造堆的效率是多少？ O(n) 2 刪除最大鍵及后續(xù)的效率刪除最大鍵及后續(xù)的效率 O(nlogn) 評(píng)價(jià)：評(píng)價(jià)： 堆排序不需任何額外的存儲(chǔ)空間堆排序不需任何額外的存儲(chǔ)空間 針對(duì)隨機(jī)文件的實(shí)驗(yàn)指出，堆排序比快速排序運(yùn)針對(duì)隨機(jī)文件的實(shí)驗(yàn)指出，堆排序比快速排序運(yùn)行的慢，但和合并排序還是有競(jìng)爭(zhēng)力的。行的慢，但和合并排序還是有競(jìng)爭(zhēng)力的。44 實(shí)例化簡(jiǎn)實(shí)例化簡(jiǎn)-AVL

26、樹樹 查找效率最壞查找效率最壞 平均平均 改變表現(xiàn)改變表現(xiàn)-2-3樹樹 查找效率最壞，平均查找效率最壞，平均 堆堆 兩種構(gòu)造方法的效率兩種構(gòu)造方法的效率 刪除的效率刪除的效率 堆排序堆排序 效率效率456.5.1 Horner法則法則 計(jì)算計(jì)算n次多項(xiàng)式的值的算法。次多項(xiàng)式的值的算法。 例如，例如，n=4, 直接計(jì)算，需要多少次乘法？直接計(jì)算，需要多少次乘法？ 4+3+2+1=10=n(n-1)/2次乘法，次乘法， 用如下用如下Horner/秦九韶算法只需要秦九韶算法只需要4=n次乘法：次乘法：5) 1) 3) 12( 532)(234xxxxxxxxxp465) 1)3) 12( 532)(

27、234xxxxxxxxxp當(dāng)當(dāng)x=3時(shí)，計(jì)算時(shí)，計(jì)算p(x)系數(shù)系數(shù)2-131-5X=3223+(-1)=553+3=18518+1=55553+(-5)=160霍納法則的有趣特性霍納法則的有趣特性該算法在計(jì)算該算法在計(jì)算p(x)在某些點(diǎn)在某些點(diǎn)x0上的值所產(chǎn)生的上的值所產(chǎn)生的中間數(shù)字中間數(shù)字恰好可以恰好可以作為作為p(x)除以除以x-x0的商的系數(shù)的商的系數(shù)，而算法的最后結(jié)果，除了等于，而算法的最后結(jié)果，除了等于p(x0)以外，還等于這個(gè)除法的余數(shù)。以外，還等于這個(gè)除法的余數(shù)。即，當(dāng)即，當(dāng)x0=3時(shí)時(shí) p(x)=2x4-x3-3x2+x-5 除以除以x-3為為2x3+5x2+18x+55 和

28、和 16047 6.5.2 二進(jìn)制冪二進(jìn)制冪 計(jì)算計(jì)算an的算法，有兩種方法：的算法，有兩種方法： n的二進(jìn)制中間結(jié)果1101aa2*a=a3(a6)2*a=a13(a2)2=a6n的二進(jìn)制中間結(jié)果1101aaa*a4=a5a5*a8=a13a8a4a2a2i的值48問(wèn)題化簡(jiǎn)是一個(gè)重要的解題策略問(wèn)題化簡(jiǎn)是一個(gè)重要的解題策略如解析幾何的根本思想是把幾何問(wèn)題化為代數(shù)問(wèn)如解析幾何的根本思想是把幾何問(wèn)題化為代數(shù)問(wèn)題題49原問(wèn)題：原問(wèn)題： 求能夠被求能夠被m和和n整除的最小整數(shù)記為整除的最小整數(shù)記為lcm(m,n)常用算法：常用算法： m和和n所有公共質(zhì)因數(shù)乘以所有公共質(zhì)因數(shù)乘以m的不在的不在n中的質(zhì)因

29、數(shù)，中的質(zhì)因數(shù)，再乘以再乘以n不在不在m中的質(zhì)因數(shù)中的質(zhì)因數(shù) 24=2223 60=2235 lcm(24,60)=(223)25=120缺陷：缺陷： 需要連續(xù)素?cái)?shù)的表需要連續(xù)素?cái)?shù)的表50關(guān)聯(lián)關(guān)聯(lián) m和和n的的最大公約數(shù)最大公約數(shù)gcd(m,n)是是m和和n所有公共質(zhì)所有公共質(zhì)因子的積。因子的積。并且并且lcm(m,n)=mn/gcd(m,n)問(wèn)題化簡(jiǎn)問(wèn)題化簡(jiǎn) 轉(zhuǎn)換為求最大公約數(shù)轉(zhuǎn)換為求最大公約數(shù)gcd(m,n)的高效的歐幾里德的高效的歐幾里德算法算法51原問(wèn)題：原問(wèn)題： 計(jì)算圖中兩個(gè)頂點(diǎn)之間的路徑數(shù)量計(jì)算圖中兩個(gè)頂點(diǎn)之間的路徑數(shù)量問(wèn)題化簡(jiǎn)：?jiǎn)栴}化簡(jiǎn)： 可利用鄰接矩陣，可以證明：可利用鄰接矩陣

30、，可以證明： 圖圖G中頂點(diǎn)中頂點(diǎn)vi到頂點(diǎn)到頂點(diǎn)vj之間長(zhǎng)度為之間長(zhǎng)度為k的路徑數(shù)的路徑數(shù)量等于量等于AK的第的第(i,j)個(gè)元素個(gè)元素，其中，其中A是圖是圖G的的鄰接矩陣。鄰接矩陣。52原問(wèn)題：原問(wèn)題： 求函數(shù)的最大值或最小值求函數(shù)的最大值或最小值 問(wèn)題化簡(jiǎn)：?jiǎn)栴}化簡(jiǎn)： 已知函數(shù)的最大值的算法已知函數(shù)的最大值的算法 求其最小值求其最小值 min f(x)=-max-f(x) 函數(shù)最優(yōu)化：函數(shù)最優(yōu)化： 把最優(yōu)化問(wèn)題轉(zhuǎn)化為函數(shù)極值問(wèn)題，再由把最優(yōu)化問(wèn)題轉(zhuǎn)化為函數(shù)極值問(wèn)題，再由 f(x)=0求臨界點(diǎn)。求臨界點(diǎn)。53許多許多決策優(yōu)化問(wèn)題決策優(yōu)化問(wèn)題可以轉(zhuǎn)化為可以轉(zhuǎn)化為線性規(guī)劃線性規(guī)劃問(wèn)題。問(wèn)題。例子

31、：進(jìn)行例子：進(jìn)行1億美元的投資。該筆錢分成億美元的投資。該筆錢分成3種類型種類型的投資：股票、債券和現(xiàn)金。預(yù)期收益各是的投資：股票、債券和現(xiàn)金。預(yù)期收益各是10%，7%，3%。并且投資在股票上的資金不能超過(guò)債。并且投資在股票上的資金不能超過(guò)債券的券的1/3，現(xiàn)金投資至少相當(dāng)于股票和債券投資，現(xiàn)金投資至少相當(dāng)于股票和債券投資總額的總額的25%。這筆投資如何才能最大化收益？。這筆投資如何才能最大化收益？54線性規(guī)劃問(wèn)題是一個(gè)線性規(guī)劃問(wèn)題是一個(gè)多變量線性函數(shù)多變量線性函數(shù)的最優(yōu)化問(wèn)的最優(yōu)化問(wèn)題。題。這些變量要滿足的約束是以這些變量要滿足的約束是以線性等式線性等式或或線性不等線性不等式式的形式出現(xiàn)。的

32、形式出現(xiàn)?？梢詾楦鞣N應(yīng)用建模，如排班，交通和通信網(wǎng)絡(luò)可以為各種應(yīng)用建模，如排班，交通和通信網(wǎng)絡(luò)規(guī)劃，石油勘探和提純。規(guī)劃，石油勘探和提純。解線性規(guī)劃問(wèn)題的算法：解線性規(guī)劃問(wèn)題的算法： 單純形法單純形法 Karmarkar算法算法55 整數(shù)線性規(guī)劃問(wèn)題：把變量的值限定在整數(shù)。整數(shù)線性規(guī)劃問(wèn)題：把變量的值限定在整數(shù)。 目前還沒(méi)有一個(gè)已知的多項(xiàng)式級(jí)的求解算法。目前還沒(méi)有一個(gè)已知的多項(xiàng)式級(jí)的求解算法。56 許多問(wèn)題用圖表示后，求解很容易。通常用圖的許多問(wèn)題用圖表示后，求解很容易。通常用圖的頂頂點(diǎn)點(diǎn)表示問(wèn)題的表示問(wèn)題的狀態(tài)狀態(tài)，邊邊表示狀態(tài)之間的可能表示狀態(tài)之間的可能轉(zhuǎn)變轉(zhuǎn)變。表。表示問(wèn)題的圖稱為示問(wèn)題的圖稱為狀態(tài)空間圖狀態(tài)空間圖。 例如例如過(guò)河問(wèn)題過(guò)河問(wèn)題： 一個(gè)農(nóng)夫希望用一條小船把一只一個(gè)農(nóng)夫希望用一條小船把一只狼狼，一頭，一頭羊羊，一籃，一籃白菜白菜從河的北岸渡到河的南岸，由于船小只能夠容納從河的北岸渡到河的南