算法設(shè)計與分析變治法2021最全課件

算法設(shè)計與分析變治法1算法設(shè)計與分析變治法1

（1）實例化簡——同樣問題

6.1預(yù)排序

6.2高斯消去法

6.3平衡查找樹—AVL樹（2）改變表現(xiàn)——同樣實例6.32-3樹6.4堆和堆排序

6.5霍納法則和二進制冪（3）問題化簡——另一問題6.62（1）實例化簡——同樣問題26.1預(yù)排序列表是有序的話，許多關(guān)于列表的問題更容易求解。因此很多問題需要先排序，則該問題的時間效率依賴于排序算法的效率。回憶前面所學(xué)的排序算法：插入排序最差Θ(n2)平均Θ(n2)最優(yōu)Θ(n)快速排序最差Θ(n2)平均Θ(1.38nlog2n)最優(yōu)Θ(nlog2n)合并排序最差Θ(nlog2n)選擇排序 Θ(n2)冒泡排序 Θ(n2)36.1預(yù)排序列表是有序的話，許多關(guān)于列表的問題更容易求解效率若有n個關(guān)鍵字，構(gòu)成一棵全部由3節(jié)點構(gòu)成的滿樹，n與h之間的關(guān)系為？5堆中刪除元素的算法3自底向上構(gòu)造法的時間效率所能想到的求模式的方法：3最差情況是一種什么情況？高斯消去法的現(xiàn)代商業(yè)實現(xiàn)是以LU分解為基礎(chǔ)的。1二叉查找樹的特點是？一般的線性方程組是指如下形式的方程組：考慮一種既能夠保留經(jīng)典二叉查找樹的好特性//輸入：數(shù)組A模式：指數(shù)組列表中出現(xiàn)次數(shù)最多的值。//輸出：方程組的增廣矩陣等價的上三角矩陣在最差情況下查找和插入的效率屬于Θ(logn)針對隨機文件的實驗指出，堆排序比快速排序運行的慢，但和合并排序還是有競爭力的。7,6,5,2兩種構(gòu)造方法的效率對于隨機鍵的列表構(gòu)造的AVL樹，得到它的平均高度的精確公式被證明是有難度的。例1、檢驗數(shù)組中元素的唯一性

蠻力法如何做？時間效率是多少？如果先排序，則如何檢查元素的唯一性？只需檢查相互緊挨的元素。PresortElementUniqueness(A[0..n-1])//先對數(shù)組排序再驗證唯一性//輸入：數(shù)組A//輸出：若A沒有相等的元素，返回“true”,否則返回“false”.

對數(shù)組排序；

fori=0ton-2doifA[i]=A[i+1]returnfalse

returntrue整個過程時間效率是多少？4效率例1、檢驗數(shù)組中元素的唯一性整個過程時間效率是多少？4預(yù)排序例2、模式計算模式：指數(shù)組列表中出現(xiàn)次數(shù)最多的值。如{5,1,5,7,6,5,7}中5是模式所能想到的求模式的方法：用輔助列表列出所有元素及其出現(xiàn)頻率。時間效率如何分析？采用排序的思想先排序后計算相鄰接次數(shù)最多的等值元素。時間效率如何分析？5預(yù)排序例2、模式計算5思考：預(yù)排序還可以用在什么方面？查找分析順序查找和先排序再查找的時間效率如果要在同一個列表中進行多次查找，在排序上花費時間是值得的。課堂練習：采用合并排序為預(yù)排序，折半查找，要做多少次查找才能使得對一個由n個元素構(gòu)成的數(shù)組所做的預(yù)排序是有意義的。6思考：預(yù)排序還可以用在什么方面？6預(yù)排序的其他應(yīng)用：對點排序，拓撲排序課堂練習：P15347預(yù)排序的其他應(yīng)用：76.2Gauss消去法科學(xué)計算中通常需要解多個變量的方程組，這些方程組當中最簡單的是線性方程組，也就是變量的次數(shù)均為1次的。求解線性方程的方法有利用高斯消元的直接法以及迭代法。體現(xiàn)的變治的思想：

將方程組變成一個具有特殊性質(zhì)的方程組(上三角矩陣)86.2Gauss消去法科學(xué)計算中通常需要解多個變量的方1、高斯消元法一般的線性方程組是指如下形式的方程組：91、高斯消元法一般的線性方程組是指如下形式的方程組：9高斯消元法分消元過程和回代過程。消元過程將原方程組變?yōu)樯先欠匠探M，回代過程得到方程組的解。10高斯消元法分消元過程和回代過程。消元過程將原方高斯消元法舉例：11高斯消元法舉例：11高斯消元法的偽代碼

GaussElimination(A[1..n],b[1..n])//輸入：系數(shù)矩陣A及常數(shù)項b//輸出：方程組的增廣矩陣等價的上三角矩陣fori=1tondo

A[i][n+1]=b[i]fori=1ton-1do forj=i+1tondofork=iton+1doA[j][k]=A[j][k]–A[i][k]*A[j][i]/A[i][i]12高斯消元法的偽代碼GaussElimination(A[高斯消元法的效率分析基本操作：乘法執(zhí)行次數(shù)：易見，三重循環(huán)

C(n)∈Θ(n3)13高斯消元法的效率分析132、LU分解法高斯消去法的現(xiàn)代商業(yè)實現(xiàn)是以LU分解為基礎(chǔ)的。142、LU分解法高斯消去法的現(xiàn)代商業(yè)實現(xiàn)是以LU分解為基礎(chǔ)的。

系數(shù)矩陣為下三角矩陣L，由主對角線上的1以及在高斯消去過程中行的乘數(shù)構(gòu)成上三角矩陣U是消去的結(jié)果可觀察出兩個矩陣的乘積LU等于A15系數(shù)矩陣為下三角矩陣L，由主對角線上的1上三角矩陣U是消去記原方程組為AX=b

A=LU則原方程組為LUX=b其求解轉(zhuǎn)化為兩個三角形方程組的求解：

LY=b——下三角方程組UX=Y——上三角方程組16記原方程組為AX=b16LU分解法與LY=b,UX=Y對應(yīng)的方程組如下：易得：

(y1,y2,y3)=(1,3,-2),(x1,x2,x3)=(1,0,-1)17LU分解法與LY=b,UX=Y對應(yīng)的方程組如下：易得：17評價1一旦的到矩陣A的LU分解，無論對于什么樣的右邊向量b，我們都可以對方程組Ax=b求解，每次求一個。2LU分解不需要額外的存儲空間18評價1一旦的到矩陣A的LU分解，無論對于什么樣的右邊向量b3、計算矩陣的逆逆矩陣的定義：求矩陣A的逆矩陣，如何轉(zhuǎn)換193、計算矩陣的逆逆矩陣的定義：求矩陣A的逆矩陣，如何轉(zhuǎn)換計算矩陣的逆求矩陣A的逆矩陣，轉(zhuǎn)化為求解n個方程組

AXj=bj其中，bj是單位矩陣的第j列，而Xj則是逆矩陣的第j列。20計算矩陣的逆求矩陣A的逆矩陣，轉(zhuǎn)化為求解n個方程組203、計算矩陣的行列式n階矩陣的行列式的計算由遞歸公式定義：

其中，n=1時，detA=a11，若j為奇數(shù)，sj=1，若j為偶數(shù)，sj=-1例如n=3的情形如下：213、計算矩陣的行列式n階矩陣的行列式的計算由遞歸公式定義：2計算矩陣行列式按照定義計算高階行列式是不可能的?？衫酶咚瓜ǎ壕仃嘇的行列式=消元后上三角矩陣的行列式=對角線上元素之乘積。例如，上式中detA=2·3·2=1222計算矩陣行列式按照定義計算高階行列式是不可能的。22課堂練習：考慮高斯消去法的反向替換的運行時間效率類型是多少？23課堂練習：236.3平衡查找樹二叉查找樹是一種重要的數(shù)據(jù)結(jié)構(gòu)看書p162-163，思考下列問題：1二叉查找樹的特點是？2在平均情況下，查找，插入，刪除的效率是？3最差情況是一種什么情況？4最差情況效率是多少？246.3平衡查找樹二叉查找樹是一種重要的數(shù)據(jù)結(jié)構(gòu)24把一個集合變換成一棵二叉查找樹是改變表現(xiàn)技術(shù)的一個實例好處是：在平均情況下，查找，插入，刪除的效率是Θ(logn)最差情況下，Θ(n)，退化成線性的情況25把一個集合變換成一棵二叉查找樹是改變表現(xiàn)技術(shù)的一個實例25考慮一種既能夠保留經(jīng)典二叉查找樹的好特性又能夠避免它退化到最差情況的數(shù)據(jù)結(jié)構(gòu)兩種方法：實例化簡：不平衡二叉查找樹變?yōu)槠胶獾男问礁淖儽憩F(xiàn)：允許一棵查找樹的單個節(jié)點中不止包含一個元素。26考慮一種既能夠保留經(jīng)典二叉查找樹的好特性26看書p163,p166回憶及思考下面問題1AVL樹的概念2AVL樹查找效率與什么相關(guān)？3最差情況27看書p163,p166回憶及思考下面問題27AVL樹的效率評價n個節(jié)點的AVL樹的高度h對于隨機鍵的列表構(gòu)造的AVL樹，得到它的平均高度的精確公式被證明是有難度的。實驗表明，這個高度大約是1.01log2n+0.1在平均情況下，查找一棵AVL樹需要的比較次數(shù)和用折半查找一個有序數(shù)組是幾乎相同的。在最差情況下查找和插入的效率屬于Θ(logn)缺點：頻繁的旋轉(zhuǎn)，維護平衡以及總體上的復(fù)雜性28AVL樹的效率評價n個節(jié)點的AVL樹的高度h28樹

2-3樹是一種特殊的高度平衡樹，允許結(jié)點最多包含兩個關(guān)鍵字。兩類結(jié)點：2-node、3-node。樹中所有葉子必須位于同一層。29樹2-3樹是一種特殊的高度平衡樹，允許結(jié)點最多包含兩個關(guān)2-3樹的搜索與插入看書理解1搜索算法p1672插入算法p168302-3樹的搜索與插入看書理解30搜索算法如果待搜索樹的根是2-node型結(jié)點，搜索操作與二叉搜索樹搜索操作相同；如果待搜索樹的根是3-node型結(jié)點，最多只需要比較兩次就可以知道是搜索成功還是需要向3棵子樹繼續(xù)遞歸搜索。31搜索算法31插入算法：當一個結(jié)點x需要插入到2-3樹中的時候，總是根據(jù)它的大小關(guān)系，把其插入到葉結(jié)點中。插入前首先調(diào)用搜索算法找到待插入的葉結(jié)點，如果該葉結(jié)點是2-node型的，則直接插入即可；如果該葉結(jié)點是3-node型的，在按序插入到葉結(jié)點后，需要把葉結(jié)點拆分（因為插入后使得葉結(jié)點的關(guān)鍵字個數(shù)為3，不滿足2-3樹的要求）。拆分過程首先在三個關(guān)鍵字挑選值在中間的關(guān)鍵字，提到上一層，或者作為新結(jié)點，或者插入原來的內(nèi)結(jié)點中；關(guān)鍵字最小的作為左子樹，關(guān)鍵字最大的作為右子樹。如果內(nèi)結(jié)點的插入導(dǎo)致結(jié)點過大，按照上述規(guī)則繼續(xù)拆分。32插入算法：322-3樹的效率分析操作效率與什么相關(guān)？樹高h若有n個關(guān)鍵字，構(gòu)成一棵全部由2節(jié)點構(gòu)成的滿樹，n與h之間的關(guān)系為？若有n個關(guān)鍵字，構(gòu)成一棵全部由3節(jié)點構(gòu)成的滿樹，n與h之間的關(guān)系為？

所以高度的范圍是：

無論在最差還是平均，查找，插入和刪除時間效率都是對數(shù)類型332-3樹的效率分析操作效率與什么相關(guān)？336.4堆和堆排序堆的概念看書p170-p173回憶及理解1堆的定義2堆的構(gòu)建方法3自底向上構(gòu)造法的時間效率4自頂向下構(gòu)造法的時間效率5堆中刪除元素的算法346.4堆和堆排序堆的概念341堆的定義堆是一棵二叉樹，樹中節(jié)點包含鍵，滿足下面兩個條件：樹的形狀：二叉樹父母：每個節(jié)點的鍵都要大于或等于它子女的鍵。351堆的定義35

2自底向上構(gòu)造法首先把數(shù)組按序填充到堆中各個結(jié)點然后按照自下而上，從右至左的順序，從最后的父母節(jié)點開始，到根為止，檢查這些節(jié)點的值是否都滿足子結(jié)點比父結(jié)點小的約束條件。如果不滿足則調(diào)換父子結(jié)點的位置，然后再檢查在新的位置上，是不是滿足父母優(yōu)勢要求。用自底向上法為1，8，6，5，3，7，4構(gòu)造一個堆362自底向上構(gòu)造法首先把數(shù)組按序填充到堆中各個結(jié)點362自底向上構(gòu)造法最壞情況每個位于樹的第i層的鍵都會移動到葉子層h中移動到下一層需要進行幾次比較？兩次。位于第i層的鍵移到葉子層h需要幾次比較？需要2(h-i)次鍵值比較。因此有下式：結(jié)論:一個規(guī)模為n的堆只需不到2n次比較就能構(gòu)造完成372自底向上構(gòu)造法最壞情況373自頂向下構(gòu)造法將包含新鍵K附加在當前堆的最后一個葉子后面將新鍵和父母比較交換這個鍵向上走，直到它不大于它的父母為止用自頂向下法為1，8，6，5，3，7，4構(gòu)造一個堆思考一個新鍵插入i個元素構(gòu)成的堆的比較次數(shù)N個規(guī)模問題的比較次數(shù)383自頂向下構(gòu)造法將包含新鍵K附加在當前堆的最后一個葉子后面4堆結(jié)點的刪除只考慮刪除根中的鍵把待刪除結(jié)點與堆中最后一個鍵K對調(diào)。

執(zhí)行刪除操作并把堆的大小減一。

對刪除后的堆進行調(diào)整直到滿足堆的約束條件。刪除的效率分析：取決于交換和規(guī)模減一后，樹的堆化所需的鍵值比較次數(shù)。因為鍵值比較次數(shù)不可能超過堆的高度的兩倍，刪除的時間也是屬于對數(shù)類型的。

394堆結(jié)點的刪除只考慮刪除根中的鍵39堆排序堆排序主要包括兩個步驟：(1)對于給定的數(shù)組構(gòu)造相應(yīng)的堆。(2)對所構(gòu)造的堆執(zhí)行n-1次刪除堆的根結(jié)點的操作，把刪除得到的結(jié)點保存在給定數(shù)組中。

40堆排序堆排序主要包括兩個步驟：40堆排序舉例用堆排序?qū)?shù)組{2，9，7，6，5，8}排序步驟1：構(gòu)造堆

2,9,7,6,5,82,9,8,6,5,7

2,9,8,6,5,79,2,8,6,5,7

9,6,8,2,5,741堆排序舉例用堆排序?qū)?shù)組{2，9，7，6，5，8}排序41堆排序舉例步驟2：刪除根結(jié)點

9,6,8,2,5,77,6,8,2,5

8,6,7,2,55,6,7,2

7,6,5,22,6,5

6,5,2

5,22

42堆排序舉例步驟2：刪除根結(jié)點42堆排序效率分析1構(gòu)造堆的效率是多少？O(n)2刪除最大鍵及后續(xù)的效率O(nlogn)評價：堆排序不需任何額外的存儲空間針對隨機文件的實驗指出，堆排序比快速排序運行的慢，但和合并排序還是有競爭力的。43堆排序效率分析1構(gòu)造堆的效率是多少？436.3-6.4小結(jié)實例化簡-AVL樹查找效率最壞平均改變表現(xiàn)-2-3樹查找效率最壞，平均

堆兩種構(gòu)造方法的效率刪除的效率

堆排序效率446.3-6.4小結(jié)實例化簡-AVL樹446.5Horner法則和二進制冪法則計算n次多項式的值的算法。例如，n=4,直接計算，需要多少次乘法？4+3+2+1=10=n(n-1)/2次乘法，用如下Horner/秦九韶算法只需要4=n次乘法：456.5Horner法則和二進制冪法則45當x=3時，計算p(x)系數(shù)2-131-5X=322×3+(-1)=55×3+3=185×18+1=5555×3+(-5)=160霍納法則的有趣特性該算法在計算p(x)在某些點x0上的值所產(chǎn)生的中間數(shù)字恰好可以作為p(x)除以x-x0的商的系數(shù)，而算法的最后結(jié)果，除了等于p(x0)以外，還等于這個除法的余數(shù)。即，當x0=3時p(x)=2x4-x3-3x2+x-5除以x-3為2x3+5x2+18x+55

和16046當x=3時，計算p(x)系數(shù)2-131-5X=322×3+(

二進制冪計算an的算法，有兩種方法：從左到右逐位掃描算法：例求a13,13=1101從右到左逐位掃描算法:例求a13,13=1101

47二進制冪從左到右逐位掃描算法：例求a13,13=116.6問題化簡問題化簡是一個重要的解題策略如解析幾何的根本思想是把幾何問題化為代數(shù)問題486.6問題化簡問題化簡是一個重要的解題策略48原問題：求能夠被m和n整除的最小整數(shù)記為lcm(m,n)常用算法：

m和n所有公共質(zhì)因數(shù)乘以m的不在n中的質(zhì)因數(shù)，再乘以n不在m中的質(zhì)因數(shù)

24=2×2×2×360=2×2×3×5lcm(24,60)=(2×2×3)×2×5=120缺陷：需要連續(xù)素數(shù)的表49原問題：49關(guān)聯(lián)

m和n的最大公約數(shù)gcd(m,n)是m和n所有公共質(zhì)因子的積。并且lcm(m,n)=m·n/gcd(m,n)問題化簡轉(zhuǎn)換為求最大公約數(shù)gcd(m,n)的高效的歐幾里德算法50關(guān)聯(lián)50計算圖中的路徑數(shù)原問題：計算圖中兩個頂點之間的路徑數(shù)量問題化簡：可利用鄰接矩陣，可以證明：圖G中頂點vi到頂點vj之間長度為k的路徑數(shù)量等于AK的第(i,j)個元素，其中A是圖G的鄰接矩陣。51計算圖中的路徑數(shù)原問題：51優(yōu)化問題的化簡原問題：求函數(shù)的最大值或最小值問題化簡：已知函數(shù)的最大值的算法求其最小值

minf(x)=-max[-f(x)]函數(shù)最優(yōu)化：把最優(yōu)化問題轉(zhuǎn)化為函數(shù)極值問題，再由f’(x)=0求臨界點。52優(yōu)化問題的化簡原問題：52線性規(guī)劃許多決策優(yōu)化問題可以轉(zhuǎn)化為線性規(guī)劃問題。例子：進行1億美元的投資。該筆錢分成3種類型的投資：股票、債券和現(xiàn)金。預(yù)期收益各是10%，7%，3%。并且投資在股票上的資金不能超過債券的1/3，現(xiàn)金投資至少相當于股票和債券投資總額的25%。這筆投資如何才能最大化收益？53線性規(guī)劃許多決策優(yōu)化問題可以轉(zhuǎn)化為線性規(guī)劃問題。53線性規(guī)劃問題是一個多變量線性函數(shù)的最優(yōu)化問題。這些變量要滿足的約束是以線性等式或線性不等式的形式出現(xiàn)?？梢詾楦鞣N應(yīng)用建模，如排班，交通和通信網(wǎng)絡(luò)規(guī)劃，石油勘探和提純。解線性規(guī)劃問題的算法：單純形法Karmarkar算法54線性規(guī)劃問題是一個多變量線性函數(shù)的最優(yōu)化問題。54整數(shù)線性規(guī)劃問題：把變量的值限定在整數(shù)。目前還沒有一個已知的多項式級的求解算法。55整數(shù)線性規(guī)劃問題：把變量的值限定在整數(shù)。55簡化為圖論問題許多問題用圖表示后，求解很容易。通常用圖的頂點表示問題的狀態(tài)，邊表示狀態(tài)之間的可能轉(zhuǎn)變。表示問題的圖稱為狀態(tài)空間圖。例如過河問題：一個農(nóng)夫希望用一條小船把一只狼，一頭羊，一籃白菜從河的北岸渡到河的南岸，由于船小只能夠容納人狼羊菜中的兩個。需要考慮的約束條件是：在沒有人的情況下，狼和羊不能在一起，羊和白菜不能單獨在一起。求解一個渡船的方案，把狼、羊、白菜都運過去。

56簡化為圖論問題許多問題用圖表示后，求解很容易。通常用圖對過河問題，畫出人、狼、羊、菜的狀態(tài)空間圖后即可以發(fā)現(xiàn)有兩條路徑，這兩條路徑就是問題的兩個解。57對過河問題，畫出人、狼、羊、菜的狀態(tài)空間圖后即可以發(fā)現(xiàn)有兩條過河問題解：用四維0-1向量表示(人,狼,羊,菜)在河西岸的狀態(tài)(在河西岸則分量取1,否則取0),共有24=16種狀態(tài).在河?xùn)|岸的狀態(tài)類似記作.由題設(shè),狀態(tài)(0,1,1,0),(0,0,1,1),(0,1,1,1)是不允許的,從而對應(yīng)狀態(tài)(1,0,0,1),(1,1,0,0),(1,0,0,0)也是不允許的.以可允許的10個狀態(tài)向量作為頂點,將可能互相轉(zhuǎn)移的狀態(tài)用線段連接起來構(gòu)成一個圖.

根據(jù)此圖便可找到渡河方法.58過河問題解：用四維0-1向量表示(人,狼,羊,菜)在河西岸的(1,1,1,1)

(1,1,1,0)

(1,1,0,1)

(1,0,1,1)

(1,0,1,0)(0,0,0,0)

(0,0,0,1)

(0,0,1,0)

(0,1,0,0)

(0,1,0,1)(0,1,0,1)

(0,1,0,0)

(0,0,1,0)

(0,0,0,1)

(0,0,0,0)(1,0,1,0)

(1,0,1,1)

(1,1,0,1)

(1,1,1,0)

(1,1,1,1)河西=(人,狼,羊,菜)河?xùn)|=(人,狼,羊,菜)

將10個頂點分別記為A1,A2,…,A10,則渡河問題化為在該圖中求一條從A1到A10的路.從圖中易得到兩條路：A1A6A3A7A2A8A5A10;A1A6A3A9A4A8A5A10.59(1,1,1,1)(1,1,1,0)(1,1,0算法設(shè)計與分析變治法2021最全課件算法設(shè)計與分析變治法61算法設(shè)計與分析變治法1

（1）實例化簡——同樣問題

6.1預(yù)排序

6.2高斯消去法

6.3平衡查找樹—AVL樹（2）改變表現(xiàn)——同樣實例6.32-3樹6.4堆和堆排序

6.5霍納法則和二進制冪（3）問題化簡——另一問題6.662（1）實例化簡——同樣問題26.1預(yù)排序列表是有序的話，許多關(guān)于列表的問題更容易求解。因此很多問題需要先排序，則該問題的時間效率依賴于排序算法的效率。回憶前面所學(xué)的排序算法：插入排序最差Θ(n2)平均Θ(n2)最優(yōu)Θ(n)快速排序最差Θ(n2)平均Θ(1.38nlog2n)最優(yōu)Θ(nlog2n)合并排序最差Θ(nlog2n)選擇排序 Θ(n2)冒泡排序 Θ(n2)636.1預(yù)排序列表是有序的話，許多關(guān)于列表的問題更容易求解效率若有n個關(guān)鍵字，構(gòu)成一棵全部由3節(jié)點構(gòu)成的滿樹，n與h之間的關(guān)系為？5堆中刪除元素的算法3自底向上構(gòu)造法的時間效率所能想到的求模式的方法：3最差情況是一種什么情況？高斯消去法的現(xiàn)代商業(yè)實現(xiàn)是以LU分解為基礎(chǔ)的。1二叉查找樹的特點是？一般的線性方程組是指如下形式的方程組：考慮一種既能夠保留經(jīng)典二叉查找樹的好特性//輸入：數(shù)組A模式：指數(shù)組列表中出現(xiàn)次數(shù)最多的值。//輸出：方程組的增廣矩陣等價的上三角矩陣在最差情況下查找和插入的效率屬于Θ(logn)針對隨機文件的實驗指出，堆排序比快速排序運行的慢，但和合并排序還是有競爭力的。7,6,5,2兩種構(gòu)造方法的效率對于隨機鍵的列表構(gòu)造的AVL樹，得到它的平均高度的精確公式被證明是有難度的。例1、檢驗數(shù)組中元素的唯一性

蠻力法如何做？時間效率是多少？如果先排序，則如何檢查元素的唯一性？只需檢查相互緊挨的元素。PresortElementUniqueness(A[0..n-1])//先對數(shù)組排序再驗證唯一性//輸入：數(shù)組A//輸出：若A沒有相等的元素，返回“true”,否則返回“false”.

對數(shù)組排序；

fori=0ton-2doifA[i]=A[i+1]returnfalse

returntrue整個過程時間效率是多少？64效率例1、檢驗數(shù)組中元素的唯一性整個過程時間效率是多少？4預(yù)排序例2、模式計算模式：指數(shù)組列表中出現(xiàn)次數(shù)最多的值。如{5,1,5,7,6,5,7}中5是模式所能想到的求模式的方法：用輔助列表列出所有元素及其出現(xiàn)頻率。時間效率如何分析？采用排序的思想先排序后計算相鄰接次數(shù)最多的等值元素。時間效率如何分析？65預(yù)排序例2、模式計算5思考：預(yù)排序還可以用在什么方面？查找分析順序查找和先排序再查找的時間效率如果要在同一個列表中進行多次查找，在排序上花費時間是值得的。課堂練習：采用合并排序為預(yù)排序，折半查找，要做多少次查找才能使得對一個由n個元素構(gòu)成的數(shù)組所做的預(yù)排序是有意義的。66思考：預(yù)排序還可以用在什么方面？6預(yù)排序的其他應(yīng)用：對點排序，拓撲排序課堂練習：P153467預(yù)排序的其他應(yīng)用：76.2Gauss消去法科學(xué)計算中通常需要解多個變量的方程組，這些方程組當中最簡單的是線性方程組，也就是變量的次數(shù)均為1次的。求解線性方程的方法有利用高斯消元的直接法以及迭代法。體現(xiàn)的變治的思想：

將方程組變成一個具有特殊性質(zhì)的方程組(上三角矩陣)686.2Gauss消去法科學(xué)計算中通常需要解多個變量的方1、高斯消元法一般的線性方程組是指如下形式的方程組：691、高斯消元法一般的線性方程組是指如下形式的方程組：9高斯消元法分消元過程和回代過程。消元過程將原方程組變?yōu)樯先欠匠探M，回代過程得到方程組的解。70高斯消元法分消元過程和回代過程。消元過程將原方高斯消元法舉例：71高斯消元法舉例：11高斯消元法的偽代碼

GaussElimination(A[1..n],b[1..n])//輸入：系數(shù)矩陣A及常數(shù)項b//輸出：方程組的增廣矩陣等價的上三角矩陣fori=1tondo

A[i][n+1]=b[i]fori=1ton-1do forj=i+1tondofork=iton+1doA[j][k]=A[j][k]–A[i][k]*A[j][i]/A[i][i]72高斯消元法的偽代碼GaussElimination(A[高斯消元法的效率分析基本操作：乘法執(zhí)行次數(shù)：易見，三重循環(huán)

C(n)∈Θ(n3)73高斯消元法的效率分析132、LU分解法高斯消去法的現(xiàn)代商業(yè)實現(xiàn)是以LU分解為基礎(chǔ)的。742、LU分解法高斯消去法的現(xiàn)代商業(yè)實現(xiàn)是以LU分解為基礎(chǔ)的。

系數(shù)矩陣為下三角矩陣L，由主對角線上的1以及在高斯消去過程中行的乘數(shù)構(gòu)成上三角矩陣U是消去的結(jié)果可觀察出兩個矩陣的乘積LU等于A75系數(shù)矩陣為下三角矩陣L，由主對角線上的1上三角矩陣U是消去記原方程組為AX=b

A=LU則原方程組為LUX=b其求解轉(zhuǎn)化為兩個三角形方程組的求解：

LY=b——下三角方程組UX=Y——上三角方程組76記原方程組為AX=b16LU分解法與LY=b,UX=Y對應(yīng)的方程組如下：易得：

(y1,y2,y3)=(1,3,-2),(x1,x2,x3)=(1,0,-1)77LU分解法與LY=b,UX=Y對應(yīng)的方程組如下：易得：17評價1一旦的到矩陣A的LU分解，無論對于什么樣的右邊向量b，我們都可以對方程組Ax=b求解，每次求一個。2LU分解不需要額外的存儲空間78評價1一旦的到矩陣A的LU分解，無論對于什么樣的右邊向量b3、計算矩陣的逆逆矩陣的定義：求矩陣A的逆矩陣，如何轉(zhuǎn)換793、計算矩陣的逆逆矩陣的定義：求矩陣A的逆矩陣，如何轉(zhuǎn)換計算矩陣的逆求矩陣A的逆矩陣，轉(zhuǎn)化為求解n個方程組

AXj=bj其中，bj是單位矩陣的第j列，而Xj則是逆矩陣的第j列。80計算矩陣的逆求矩陣A的逆矩陣，轉(zhuǎn)化為求解n個方程組203、計算矩陣的行列式n階矩陣的行列式的計算由遞歸公式定義：

其中，n=1時，detA=a11，若j為奇數(shù)，sj=1，若j為偶數(shù)，sj=-1例如n=3的情形如下：813、計算矩陣的行列式n階矩陣的行列式的計算由遞歸公式定義：2計算矩陣行列式按照定義計算高階行列式是不可能的?？衫酶咚瓜ǎ壕仃嘇的行列式=消元后上三角矩陣的行列式=對角線上元素之乘積。例如，上式中detA=2·3·2=1282計算矩陣行列式按照定義計算高階行列式是不可能的。22課堂練習：考慮高斯消去法的反向替換的運行時間效率類型是多少？83課堂練習：236.3平衡查找樹二叉查找樹是一種重要的數(shù)據(jù)結(jié)構(gòu)看書p162-163，思考下列問題：1二叉查找樹的特點是？2在平均情況下，查找，插入，刪除的效率是？3最差情況是一種什么情況？4最差情況效率是多少？846.3平衡查找樹二叉查找樹是一種重要的數(shù)據(jù)結(jié)構(gòu)24把一個集合變換成一棵二叉查找樹是改變表現(xiàn)技術(shù)的一個實例好處是：在平均情況下，查找，插入，刪除的效率是Θ(logn)最差情況下，Θ(n)，退化成線性的情況85把一個集合變換成一棵二叉查找樹是改變表現(xiàn)技術(shù)的一個實例25考慮一種既能夠保留經(jīng)典二叉查找樹的好特性又能夠避免它退化到最差情況的數(shù)據(jù)結(jié)構(gòu)兩種方法：實例化簡：不平衡二叉查找樹變?yōu)槠胶獾男问礁淖儽憩F(xiàn)：允許一棵查找樹的單個節(jié)點中不止包含一個元素。86考慮一種既能夠保留經(jīng)典二叉查找樹的好特性26看書p163,p166回憶及思考下面問題1AVL樹的概念2AVL樹查找效率與什么相關(guān)？3最差情況87看書p163,p166回憶及思考下面問題27AVL樹的效率評價n個節(jié)點的AVL樹的高度h對于隨機鍵的列表構(gòu)造的AVL樹，得到它的平均高度的精確公式被證明是有難度的。實驗表明，這個高度大約是1.01log2n+0.1在平均情況下，查找一棵AVL樹需要的比較次數(shù)和用折半查找一個有序數(shù)組是幾乎相同的。在最差情況下查找和插入的效率屬于Θ(logn)缺點：頻繁的旋轉(zhuǎn)，維護平衡以及總體上的復(fù)雜性88AVL樹的效率評價n個節(jié)點的AVL樹的高度h28樹

2-3樹是一種特殊的高度平衡樹，允許結(jié)點最多包含兩個關(guān)鍵字。兩類結(jié)點：2-node、3-node。樹中所有葉子必須位于同一層。89樹2-3樹是一種特殊的高度平衡樹，允許結(jié)點最多包含兩個關(guān)2-3樹的搜索與插入看書理解1搜索算法p1672插入算法p168902-3樹的搜索與插入看書理解30搜索算法如果待搜索樹的根是2-node型結(jié)點，搜索操作與二叉搜索樹搜索操作相同；如果待搜索樹的根是3-node型結(jié)點，最多只需要比較兩次就可以知道是搜索成功還是需要向3棵子樹繼續(xù)遞歸搜索。91搜索算法31插入算法：當一個結(jié)點x需要插入到2-3樹中的時候，總是根據(jù)它的大小關(guān)系，把其插入到葉結(jié)點中。插入前首先調(diào)用搜索算法找到待插入的葉結(jié)點，如果該葉結(jié)點是2-node型的，則直接插入即可；如果該葉結(jié)點是3-node型的，在按序插入到葉結(jié)點后，需要把葉結(jié)點拆分（因為插入后使得葉結(jié)點的關(guān)鍵字個數(shù)為3，不滿足2-3樹的要求）。拆分過程首先在三個關(guān)鍵字挑選值在中間的關(guān)鍵字，提到上一層，或者作為新結(jié)點，或者插入原來的內(nèi)結(jié)點中；關(guān)鍵字最小的作為左子樹，關(guān)鍵字最大的作為右子樹。如果內(nèi)結(jié)點的插入導(dǎo)致結(jié)點過大，按照上述規(guī)則繼續(xù)拆分。92插入算法：322-3樹的效率分析操作效率與什么相關(guān)？樹高h若有n個關(guān)鍵字，構(gòu)成一棵全部由2節(jié)點構(gòu)成的滿樹，n與h之間的關(guān)系為？若有n個關(guān)鍵字，構(gòu)成一棵全部由3節(jié)點構(gòu)成的滿樹，n與h之間的關(guān)系為？

所以高度的范圍是：

無論在最差還是平均，查找，插入和刪除時間效率都是對數(shù)類型932-3樹的效率分析操作效率與什么相關(guān)？336.4堆和堆排序堆的概念看書p170-p173回憶及理解1堆的定義2堆的構(gòu)建方法3自底向上構(gòu)造法的時間效率4自頂向下構(gòu)造法的時間效率5堆中刪除元素的算法946.4堆和堆排序堆的概念341堆的定義堆是一棵二叉樹，樹中節(jié)點包含鍵，滿足下面兩個條件：樹的形狀：二叉樹父母：每個節(jié)點的鍵都要大于或等于它子女的鍵。951堆的定義35

2自底向上構(gòu)造法首先把數(shù)組按序填充到堆中各個結(jié)點然后按照自下而上，從右至左的順序，從最后的父母節(jié)點開始，到根為止，檢查這些節(jié)點的值是否都滿足子結(jié)點比父結(jié)點小的約束條件。如果不滿足則調(diào)換父子結(jié)點的位置，然后再檢查在新的位置上，是不是滿足父母優(yōu)勢要求。用自底向上法為1，8，6，5，3，7，4構(gòu)造一個堆962自底向上構(gòu)造法首先把數(shù)組按序填充到堆中各個結(jié)點362自底向上構(gòu)造法最壞情況每個位于樹的第i層的鍵都會移動到葉子層h中移動到下一層需要進行幾次比較？兩次。位于第i層的鍵移到葉子層h需要幾次比較？需要2(h-i)次鍵值比較。因此有下式：結(jié)論:一個規(guī)模為n的堆只需不到2n次比較就能構(gòu)造完成972自底向上構(gòu)造法最壞情況373自頂向下構(gòu)造法將包含新鍵K附加在當前堆的最后一個葉子后面將新鍵和父母比較交換這個鍵向上走，直到它不大于它的父母為止用自頂向下法為1，8，6，5，3，7，4構(gòu)造一個堆思考一個新鍵插入i個元素構(gòu)成的堆的比較次數(shù)N個規(guī)模問題的比較次數(shù)983自頂向下構(gòu)造法將包含新鍵K附加在當前堆的最后一個葉子后面4堆結(jié)點的刪除只考慮刪除根中的鍵把待刪除結(jié)點與堆中最后一個鍵K對調(diào)。

執(zhí)行刪除操作并把堆的大小減一。

對刪除后的堆進行調(diào)整直到滿足堆的約束條件。刪除的效率分析：取決于交換和規(guī)模減一后，樹的堆化所需的鍵值比較次數(shù)。因為鍵值比較次數(shù)不可能超過堆的高度的兩倍，刪除的時間也是屬于對數(shù)類型的。

994堆結(jié)點的刪除只考慮刪除根中的鍵39堆排序堆排序主要包括兩個步驟：(1)對于給定的數(shù)組構(gòu)造相應(yīng)的堆。(2)對所構(gòu)造的堆執(zhí)行n-1次刪除堆的根結(jié)點的操作，把刪除得到的結(jié)點保存在給定數(shù)組中。

100堆排序堆排序主要包括兩個步驟：40堆排序舉例用堆排序?qū)?shù)組{2，9，7，6，5，8}排序步驟1：構(gòu)造堆

2,9,7,6,5,82,9,8,6,5,7

2,9,8,6,5,79,2,8,6,5,7

9,6,8,2,5,7101堆排序舉例用堆排序?qū)?shù)組{2，9，7，6，5，8}排序41堆排序舉例步驟2：刪除根結(jié)點

9,6,8,2,5,77,6,8,2,5

8,6,7,2,55,6,7,2

7,6,5,22,6,5

6,5,2

5,22

102堆排序舉例步驟2：刪除根結(jié)點42堆排序效率分析1構(gòu)造堆的效率是多少？O(n)2刪除最大鍵及后續(xù)的效率O(nlogn)評價：堆排序不需任何額外的存儲空間針對隨機文件的實驗指出，堆排序比快速排序運行的慢，但和合并排序還是有競爭力的。103堆排序效率分析1構(gòu)造堆的效率是多少？436.3-6.4小結(jié)實例化簡-AVL樹查找效率最壞平均改變表現(xiàn)-2-3樹查找效率最壞，平均

堆兩種構(gòu)造方法的效率刪除的效率

堆排序效率1046.3-6.4小結(jié)實例化簡-AVL樹446.5Horner法則和二進制冪法則計算n次多項式的值的算法。例如，n=4,直接計算，需要多少次乘法？4+3+2+1=10=n(n-1)/2次乘法，用如下Horner/秦九韶算法只需要4=n次乘法：1056.5Horner法則和二進制冪法則45當x=3時，計算p(x)系數(shù)2-131-5X=322×3+(-1)=55×3+3=185×18+1=5555×3+(-5)=160霍納法則的有趣特性該算法在計算p(x)在某些點x0上的值所產(chǎn)生的中間數(shù)字恰好可以作為p(x)除以x-x0的商的系數(shù)，而算法的最后結(jié)果，除了等于p(x0)以外，還等于這個除法的余數(shù)。即，當x0=3時p(x)=2x4-x3-3x2+x-5除以x-3為2x3+5x2+18x+55

和160106當x=3時，計算p(x)系數(shù)2-131-5X=322×3+(

二進制冪計算an的算法，有兩種方法：從左到右逐位掃描算法：例求a13,13=1101從右到左逐位掃描算法:例求a13,13=1101

107二進制冪從左到右逐位掃描算法：例求a13,13=116.6問題化簡問題化簡是一個重要的解題策略如解析幾何的根本思想是把幾何問題化為代數(shù)問題1086.6問題化簡問題化簡是一個重要的解題策略48原問題：求能夠被m和n整除的最小整數(shù)記為lcm(m,n)常用算法：

m和n所有公共質(zhì)因數(shù)乘以m的不在n中的質(zhì)因數(shù)，再乘以n不在m中的質(zhì)因數(shù)

24=2×2×2×360=2×2×3×5lcm(24,60)=(2×2×3)×2×5=120缺陷：需要連續(xù)素數(shù)的表109原問題：49關(guān)聯(lián)

m和n的最大公約數(shù)gcd(m,n)是m和n所有公共質(zhì)因子的積。并且lcm(m,n)=m·n/gcd(m,n)問題化簡轉(zhuǎn)換為求最大公約數(shù)gcd(m,n)的高效的歐幾里德算法110關(guān)聯(lián)50計算圖中的路徑數(shù)原問題：計算圖中兩個頂點之間的路徑數(shù)量問題