算法設(shè)計(jì)技巧與分析吳偉昶電子教案(PPT版本)czm-1要點(diǎn)

第1章算法分析基本概念曹霑懋caozhanmao@sohu《算法設(shè)計(jì)技巧與分析》Chapter1BasicConceptsinAlgorithmicAnalysis1.1Introductionl.2HistoricalBackground1.3BinarySearch1.3.1Analysisofthebinarysearchalgorithm1.4MergingTwoSortedLists1.5SelectinnSort1.6InsertionSort1.7Bottom-UpMergeSorting1.7.1Analysisofbottom-upmergesorting

2023/3/4華南師范高校計(jì)算機(jī)學(xué)院21.8TimeComplexity1.8.1Orderofgrowth1.8.2TheO-notation1.8.3Thefl-notationl.8.4Thee-notation1.8.5MamPles1.8.6Complekityclassesandtheo-notation1.9SpaceComplexity1.10OptimalAlgorithms2023/3/4華南師范高校計(jì)算機(jī)學(xué)院3Chapter1BasicConceptsinAlgorithmicAnalysis2023/3/4華南師范高校計(jì)算機(jī)學(xué)院41.1引言DonaldE.Knuth:計(jì)算機(jī)科學(xué)就是算法的探討.每個領(lǐng)域:依靠有效算法設(shè)計(jì)運(yùn)行時(shí)間:由例子到理論時(shí)間是衡量算法有效性的最好測度算法的幾個方面：輸入有限指令集輸出(存在?Y/N)2023/3/4華南師范高校計(jì)算機(jī)學(xué)院5算法和程序關(guān)系算法是程序設(shè)計(jì)的核心，程序設(shè)計(jì)本質(zhì)上是用特定的語言實(shí)現(xiàn)并細(xì)化構(gòu)造解決問題的算法，將其說明為計(jì)算機(jī)語言。算法是在有限步驟內(nèi)求解某一問題所運(yùn)用的一組定義明確的指令（規(guī)則）。通俗點(diǎn)說，就是計(jì)算機(jī)解題的過程。在這個過程中，無論是形成解題思路還是編寫程序，都是在實(shí)施某種算法。前者是推理實(shí)現(xiàn)的算法，后者是操作實(shí)現(xiàn)的算法。2023/3/4華南師范高校計(jì)算機(jī)學(xué)院6程序是算法用某種程序設(shè)計(jì)語言的具體實(shí)現(xiàn)。程序可以不滿足算法的有限性的性質(zhì)。例如操作系統(tǒng)，是一個在無限循環(huán)中執(zhí)行的程序，因而不是一個算法。操作系統(tǒng)的各種任務(wù)可看成是單獨(dú)的問題，每一個問題由操作系統(tǒng)中的一個子程序通過特定的算法來實(shí)現(xiàn)。該子程序得到輸出結(jié)果后便終止。

程序(Program)算法具有五個重要的特征

有窮性：算法必需執(zhí)行有限步之后結(jié)束；準(zhǔn)確性：算法的每一步必需有準(zhǔn)確的定義；輸入：算法有0個或多個輸入，以刻畫運(yùn)算對象的初始狀況；輸出：算法有一個或多個輸出，以反映對輸入數(shù)據(jù)加工后的結(jié)果。沒有輸出的算法是毫無意義的；可行性：算法原則上能夠精確地運(yùn)行，而且人們用筆和紙做有限次運(yùn)算后即可完成。2023/3/4華南師范高校計(jì)算機(jī)學(xué)院72023/3/4華南師范高校計(jì)算機(jī)學(xué)院81.2歷史背景20世紀(jì),30年頭能否用有效的過程來求解問題受到關(guān)注問題分類為:可解、不行解（存在有效過程來求解問題）計(jì)算模型：存在模型，用此模型能建立一求解某問題的算法，－－入－－可解的類模型列舉：歌德爾的遞歸函數(shù)，Church的Lamda演算，Post的波斯特機(jī)，Turing機(jī)。Church論斷：全部4個模型等效。假如一個問題在某一模型上可解，那么在其他模型上都是可解的。＝>“幾乎全部”問題都是不行解的。確定一個包含N個變量的多項(xiàng)式方程是否有整數(shù)解簡潔理由陳述：P3Top可判定性－〉可計(jì)算性理論，可解性－〉計(jì)算理論；有DigitalComputer后，對可解問題的探討的要求越來越多。程序，資源量，盡可能少運(yùn)用資源（時(shí)間，空間）的有效算法的需求。效率：指解決問題所需時(shí)間和空間排序一組元素的算法作為探討的實(shí)例表明：設(shè)計(jì)了很多有效算法，解決問題的效率將不會因其他方法而有大的提高。2023/3/4華南師范高校計(jì)算機(jī)學(xué)院9好的算法所具備的意義AfigintextbookofParallelComputing2023/3/4華南師范高校計(jì)算機(jī)學(xué)院10衡量算法性能的標(biāo)準(zhǔn)衡量算法性能一般有下面幾個標(biāo)準(zhǔn)正確性易讀性健壯性算法的時(shí)間和空間性能：高效率和低存儲空間我們這里主要探討算法的時(shí)間和空間性能，并以此作為衡量算法性能的重要標(biāo)準(zhǔn)。而且我們主要側(cè)重于時(shí)間方面。2023/3/4華南師范高校計(jì)算機(jī)學(xué)院11

算法的表達(dá)機(jī)制【表達(dá)算法的抽象機(jī)制】對于一個明確的數(shù)學(xué)問題，設(shè)計(jì)它的算法，總是先選用該問題的一個數(shù)學(xué)模型。接著，弄清該問題數(shù)學(xué)模型在已知條件下的初始狀態(tài)和要求的結(jié)果狀態(tài)，以及這兩個狀態(tài)之間的隱含關(guān)系。然后探究從數(shù)據(jù)模型的已知初始狀態(tài)到達(dá)要求的結(jié)果狀態(tài)所需的運(yùn)算步驟。2023/3/4華南師范高校計(jì)算機(jī)學(xué)院12

算法的描述方法自然語言；圖表；框圖；計(jì)算機(jī)語言或程序設(shè)計(jì)語言等。如，匯編、C++、Java。1.3二分搜尋假定元素滿足：線序集合Ａ[1…n]中有ｘ嗎？從頭到尾的掃描，比較ｎ次：依次搜尋依次搜尋適合無序的集合有序的集合：BinarySearchＰ４要求能夠?qū)懗觯哼@個簡潔的算法，并分析運(yùn)算量。2023/3/4華南師范高校計(jì)算機(jī)學(xué)院132023/3/4華南師范高校計(jì)算機(jī)學(xué)院141.3-(例)線性查找的時(shí)間評估最小查找時(shí)間？最好狀況,A[1]=X平均查找時(shí)間？P(i)=1/n,Tavg(n)=n/2最大查找時(shí)間？最壞狀況,x不在A[1...n]或x=A[n],困難度為n2023/3/4華南師范高校計(jì)算機(jī)學(xué)院151.3二分搜尋及其時(shí)間困難度線性搜尋二分搜尋同數(shù)據(jù)結(jié)構(gòu)，略。但要求作為例子或問題求解。及其算法分析比較次數(shù)分析while中，ｊ次循環(huán)時(shí)剩余元素?cái)?shù)目Floor(n/2j-1)循環(huán)停止條件：找到ｘ，或當(dāng)前查找范圍的數(shù)組長度為１。最大搜尋次數(shù)：滿足Floor(n/2j-1)=1時(shí)的ｊ值即：１n/2j-1<2也即：2j-1n<2jj-1logn<jj=Floor(logn)+12023/3/4華南師范高校計(jì)算機(jī)學(xué)院162023/3/4華南師范高校計(jì)算機(jī)學(xué)院17隨堂練習(xí)設(shè)有序數(shù)組：試搜尋x=20,以及X=22.1）擬用什么法？為什么？2）試給出用你想要得算法求解的過程。參考：教材binarySearchExample1.12023/3/4華南師范高校計(jì)算機(jī)學(xué)院18二分查找的基本運(yùn)算量分析？1.4合并兩個已排序的表兩個數(shù)組A[1…q],B[q+1…r]已是有序，不妨升序下面的算法將這兩個合并為一個有序數(shù)組視察1.1：Merge將n1和n2大小的兩個數(shù)組合并成一個n＝n1+n2的數(shù)組，(n1≤n2)元素的比較次數(shù)為n1到n－1之間。特例：假如兩個數(shù)組的大小為Floor(n/2)和Ceiling(n/2),須要比較的次數(shù)在Floor(n/2)到n－1之間。2023/3/4華南師范高校計(jì)算機(jī)學(xué)院192023/3/4華南師范高校計(jì)算機(jī)學(xué)院20基本思想3個數(shù)組A[p…q],A[q+1…r],B[p…r]3個指針：s,t,ks初始化時(shí)各自指向A[p]t初始化時(shí)各自指向A[q+1]k初始化時(shí)各自指向B[p],暫存器。比較A[s],A[t],小的值存入B[k]小的指針＋1，形成新比較對，存入k＋1某組已到尾部，將另一組尚未比較的復(fù)制到BB回寫到AＭｅｒｇｅ算法2023/3/4華南師范高校計(jì)算機(jī)學(xué)院21視察結(jié)論1.2運(yùn)用算法Merge將兩個數(shù)組合并為一個大小為n的有序數(shù)組，元素賦值的次數(shù)恰好是2n2023/3/4華南師范高校計(jì)算機(jī)學(xué)院222023/3/4華南師范高校計(jì)算機(jī)學(xué)院23例子－－選擇排序1.5基本思想算法：SelectionSort視察：比較次數(shù)：n(n－1)/2,賦值次數(shù)界于0與3(n－1)之間。算法1.4選擇selectionsort，

算法1.5插入排序insertionsort算法1.4比較次數(shù)，(n－1)+…+1的連續(xù)和

復(fù)制次數(shù)：0到3（n－1）算法1.5：比較次數(shù)n－1到n(n-1)/2之間。元素賦值次數(shù)為比較次數(shù)加上n－1.2023/3/4華南師范高校計(jì)算機(jī)學(xué)院242023/3/4華南師范高校計(jì)算機(jī)學(xué)院251.5-1.6.算法時(shí)間困難度的例子[例1]依次查找算法:以元素的比較作為基本運(yùn)算?？紤]成功檢索的狀況。最好狀況下的時(shí)間困難度：(1)最壞狀況下的時(shí)間困難度：(n)在等概率前提下，平均狀況下的時(shí)間困難度：(n)[例2]干脆插入排序算法:以元素的比較作為基本運(yùn)算。最好狀況下的時(shí)間困難度：(n)最壞狀況下的時(shí)間困難度：(n2)在等概率前提下，平均狀況下的時(shí)間困難度：(n2)選擇排序P7，

插入排序P82023/3/4華南師范高校計(jì)算機(jī)學(xué)院261.7自底向上合并排序歸并排序算法基本思想（合并兩個有序表ＭＥＲＧＥ為基礎(chǔ)，把最初的輸入兩兩排序，漸漸合并為完整的有序表）簡潔的以８個數(shù)的情形做例子{9,4,5,2,1,7,4,6}由小到大，考慮的對象按層計(jì)數(shù)如１１頁圖1.4算法：BOTTOMUPSORT元素賦值次數(shù)為2np9P11,分析2023/3/4華南師范高校計(jì)算機(jī)學(xué)院27Ｐｒｏｏｆ2023/3/4華南師范高校計(jì)算機(jī)學(xué)院28例子－－插入排序1.6基本思想算法：InsertionSort比較次數(shù)：n（n－1）/2賦值次數(shù)：比較次數(shù)加n－12023/3/4華南師范高校計(jì)算機(jī)學(xué)院29強(qiáng)調(diào)例子－－1.7自底向上合并排序圖示，基本思想，P9BottomUpSort實(shí)例：性能分析：P11bottomupsort時(shí)間消耗總結(jié)2023/3/4華南師范高校計(jì)算機(jī)學(xué)院30證明bottomup時(shí)間消耗2023/3/4華南師范高校計(jì)算機(jī)學(xué)院312023/3/4華南師范高校計(jì)算機(jī)學(xué)院321.8時(shí)間困難性－階的增長衡量:P12,近似時(shí)間。比較，界限近似時(shí)間，相對于同一/不同問題的算法，估計(jì)時(shí)間相對性獨(dú)立于機(jī)器，獨(dú)立于不同語言技術(shù)上的進(jìn)步，不影響算法的時(shí)間測度方法成立基本運(yùn)算支撐的大規(guī)模輸入實(shí)例。P13圖1.5：表示運(yùn)行時(shí)間的典型函數(shù)的增長狀況P14表1.1：不同大小輸入的時(shí)間量級運(yùn)行時(shí)間比較2023/3/4華南師范高校計(jì)算機(jī)學(xué)院332023/3/4華南師范高校計(jì)算機(jī)學(xué)院341.8時(shí)間困難性－2表示BigO，定義1.2：f(n),g(n)從自然數(shù)集合到非負(fù)實(shí)數(shù)集合的兩個函數(shù)，假如存在一個自然數(shù)n0和c>0,使得n>=n0,f(n)<=cg(n)則稱f(n)為O(g(n))。由極限理論，存在，則其不發(fā)散到無窮，蘊(yùn)涵f（n）＝O（g（n））。BigOmiga1.8.3：BigTheta：1.8.4舉例：1.8.52023/3/4華南師范高校計(jì)算機(jī)學(xué)院35探討問題

從定義看，f(n)為O(g(n))和f(n)與g(n)比值的極限存在是否一回事？（即是否等價(jià)？）

對于大Omega？

對于大Theta？f(n)為O(g(n))，說明f的增長至少和g的某個常數(shù)倍一樣快。f(n)為(g(n))iffg(n)為O(f(n))2023/3/4華南師范高校計(jì)算機(jī)學(xué)院361.8.4運(yùn)行時(shí)間是(g(n))階的f(n),g(n)從自然數(shù)集合到非負(fù)實(shí)數(shù)集合的兩個函數(shù)，假如存在一個自然數(shù)n0和兩個正常數(shù)c1，c2>0,使得n>=n0,c1g(n)<=f(n)<=c2g(n)則稱f（n）為(g(n))。由極限理論，存在，則其不發(fā)散到無窮，蘊(yùn)涵f（n）＝(g(n))。SELECTIONSORT,(n2）BOTTOMUPSORT,(nlogn）2023/3/4華南師范高校計(jì)算機(jī)學(xué)院37探討：P17TopParagraph1.10最優(yōu)算法－基于比較的排序定義：??Finditin5minutes

ｐ２０Examples:排序問題中的Bottomupsortbinarymergingsort(DC)2023/3/4華南師范高校計(jì)算機(jī)學(xué)院382023/3/4華南師范高校計(jì)算機(jī)學(xué)院39

1.11-14.AlgorithmAnalysis算法分析：對于算法的時(shí)間和空間困難度進(jìn)行定量分析。分析算法時(shí)間困難度的基本步驟元運(yùn)算考察可以做基本運(yùn)算的有那些，選基本運(yùn)算基本運(yùn)算的總量評估借助數(shù)學(xué)公式，比如循環(huán)嵌套就是乘法原理，遞歸調(diào)用對應(yīng)遞歸公式等求解2023/3/4華南師范高校計(jì)算機(jī)學(xué)院40簡例－－估計(jì)算法運(yùn)行時(shí)間算法時(shí)間困難度的有關(guān)概念：Ｏ，，，平均分析、求解算法困難度的基本方法設(shè)計(jì)計(jì)算過程如下：（為探討便利，每行前加一行號）

(1)fori:=1ton

(2)forj:=1ton

(3)x:=x+1

試問在程序運(yùn)行中各步執(zhí)行的次數(shù)各為多少？上例中的賦值操作或者加法可以選為基本運(yùn)算時(shí)間困難性可粗略地表示為f(n)=O(n2)。要更多地了解關(guān)于算法的困難性，就必需弄清晰如下兩個問題：(1)用怎樣的一個量來表達(dá)一個算法的困難性；

(2)對于給定的一個算法，怎樣具體計(jì)算它的困難性。2023/3/4華南師范高校計(jì)算機(jī)學(xué)院41思索與練習(xí)：指出下面程序段中語句標(biāo)[*]的頻度和該程序段的時(shí)間困難性。

(1)[*]

y:=sin(x);

(2)

fori:=1ton-1do

[*]y:=y+1;

forj:=0to2*ndo

[*]

x:=x+1;

(3)

x:=1;y:=1;

fork:=1tondo[*]x:=x+1;

fori:=1tondo

forj:=1tondo[*]y:=y+1;

(4)

i:=1;

while(i<n&&x!=A[i])do

[*]i:=i+1;ifA[i]=xthenretun(i)可否改造（4）？試練習(xí)分析下面的算法的計(jì)算量的O，，漸近表示Fori=1tonfactorial(i)=i×factorial(i-1)Endfor2023/3/4華南師范高校計(jì)算機(jī)學(xué)院422023/3/4華南師范高校計(jì)算機(jī)學(xué)院43算法困難性再回首算法的困難性是算法效率的度量，是評價(jià)算法優(yōu)劣的重要依據(jù)。一個算法的困難性的凹凸體現(xiàn)在運(yùn)行該算法所須要的計(jì)算機(jī)資源的多少上面，所需的資源越多，我們就說該算法的困難性越高；反之，所需的資源越低，則該算法的困難性越低。計(jì)算機(jī)的資源，最重要的是時(shí)間和空間（即存儲器）資源。因而，算法的困難性有時(shí)間困難性和空間困難性之分。對于隨意給定的問題，設(shè)計(jì)出困難性盡可能低的算法是我們在設(shè)計(jì)算法時(shí)追求的一個重要目標(biāo)；另一方面，當(dāng)給定的問題已有多種算法時(shí)，選擇其中困難性最低者，是我們在選用算法適應(yīng)遵循的一個重要準(zhǔn)則。算法的困難性分析的意義：對算法的設(shè)計(jì)或選用有著重要的指導(dǎo)意義和好用價(jià)值。對算法的分析，以確定或推斷算法的優(yōu)劣，通常以時(shí)間困難性來衡量，時(shí)間困難性越低，對應(yīng)的算法就越優(yōu)。2023/3/4華南師范高校計(jì)算機(jī)學(xué)院44算法的困難性分析–附加5個說明1.算法困難性概述算法困難性=算法所須要的計(jì)算機(jī)資源。算法的時(shí)間困難性T(n)；算法的空間困難性S(n)。其中n是問題實(shí)例（Instance)的規(guī)模（輸入大?。?.算法的時(shí)間復(fù)雜性（1）最壞情況下的時(shí)間復(fù)雜性

Tmax(n)=max{T(I)|size(I)=n}（2）最好情況下的時(shí)間復(fù)雜性

Tmin(n)=min{T(I)|size(I)=n}（3）平均情況下的時(shí)間復(fù)雜性

Tavg(n)=

其中I是問題的規(guī)模為n的實(shí)例，p(I)是實(shí)例I出現(xiàn)的概率。2023/3/4華南師范高校計(jì)算機(jī)學(xué)院453.算法漸近困難性T(n),asn;(T(n)-t(n))/T(n)0，asn;t(n)是T(n)的漸近性態(tài)，為算法的漸近困難性。在數(shù)學(xué)上，t(n)是T(n)的漸近表達(dá)式，是T(n)略去低階項(xiàng)留下的主項(xiàng)。它比T(n)簡潔。4.漸近困難性分析的記號Ο：漸近上界記號（ab）Ω：漸近下界記號（ab）θ：漸近同階記號（a=b）2023/3/4華南師范高校計(jì)算機(jī)學(xué)院465.漸近運(yùn)算規(guī)則O(f(n))+O(g(n))=O(max{f(n),g(n)})；O(f(n))+O(g(n))=O(f(n)+g(n))；O(f(n))*O(g(n))=O(f(n)*g(n))；O(cf(n))=O(f(n))；g(n)=O(f(n))O(f(n))+O(g(n))=O(f(n))。2023/3/4華南師范高校計(jì)算機(jī)學(xué)院471.8.2漸近表示的記號—O

-記號定義１.2Ｐ１５設(shè)f(n)和g(n)均是從自然數(shù)集到非負(fù)實(shí)數(shù)集上的函數(shù)。假如存在常數(shù)c>0和一個自然數(shù)n0，使得對于nn0，均f(n)cg(n),則稱f(n)=O(g(n))。（充分性）假如f(n)/g(n)關(guān)于ｎ極限存在，那么就有f(n)=O(g(n))。

2023/3/4華南師范高校計(jì)算機(jī)學(xué)院48１.8.3漸近表示的記號—-記號設(shè)f(n)和g(n)均是從自然數(shù)集到非負(fù)實(shí)數(shù)集上的函數(shù)。假如存在常數(shù)c>0和一個自然數(shù)n0，使得對于隨意的nn0，均有f(n)cg(n),則f(n)=(g(n))。2023/3/4華南師范高校計(jì)算機(jī)學(xué)院491.8.4漸近表示的記號—-記號設(shè)f(n)和g(n)均是從自然數(shù)集到非負(fù)實(shí)數(shù)集上的函數(shù)。假如存在一個自然數(shù)n0和兩個正常數(shù)c1，c2，使得對于隨意的nn0，均有c1g(n)f(n)c2g(n),則f(n)=(g(n))。1.8.6困難性類與o符號Ｐ１９，定義１.5無窮小o留意，用<表示f(n)是g(n)的無窮小關(guān)系，教材１９頁困難性類的層次。2023/3/4華南師范高校計(jì)算機(jī)學(xué)院50增長速度的一個鏈2023/3/4華南師范高校計(jì)算機(jī)學(xué)院51ｎ趨于無窮大時(shí)，<的前項(xiàng)是后項(xiàng)的高階無窮小2023/3/4華南師范高校計(jì)算機(jī)學(xué)院52[例1]設(shè)f(n)=10n2+20n。則有f(n)=O(n2)f(n)=(n2)f(n)=(n2)[例2]設(shè)f(n)=aknk+ak-1nk-1+…+a1n+a0,(ak>0)。則有f(n)=O(nk)f(n)=(nk)：f(n)=(nk)由此可見，困難度的漸近表示可以簡潔地表示出困難度的數(shù)量級別。漸近表示—Examples2023/3/4華南師范高校計(jì)算機(jī)學(xué)院531.8-9.算法的時(shí)間和空間困難度時(shí)間困難度（TimeComplexity）算法運(yùn)行期間所花費(fèi)的時(shí)間。通常用漸進(jìn)形式表示比如，T(n)=(n2)、(n2)或(n2)空間困難度（SpaceComplexity）在算法運(yùn)行期間所須要的內(nèi)存空間。一般指，容納輸入數(shù)據(jù)之外的附加空間（auxiliaryspace,orworkspace）。通常用漸進(jìn)形式表示比如，S(n)=(n2)、(n2)或(n2)元運(yùn)算元運(yùn)算：對任何計(jì)算步驟，其代價(jià)總是一個時(shí)間常量為上界，而不管輸入數(shù)據(jù)或執(zhí)行的算法，總稱這樣的計(jì)算步驟為元運(yùn)算，（基本操作）算術(shù)運(yùn)算：＋，—，×，/比較和邏輯運(yùn)算賦值運(yùn)算，包括遍歷表或樹的指針賦值

2023/3/4華南師范高校計(jì)算機(jī)學(xué)院542023/3/4華南師范高校計(jì)算機(jī)學(xué)院55分析時(shí)間困難度的基本步驟一、選取一種元運(yùn)算作為基本運(yùn)算二、表示出在算法運(yùn)行期間基本運(yùn)算執(zhí)行的總頻數(shù)三、漸近時(shí)間困難度（asymptotictimecomplexity）

思索因?yàn)?的n次方和8的n－1次方的比值極限當(dāng)n趨于無窮時(shí)是3，所以8n＝O（8n－1）你怎么想，結(jié)論如何？為什么你是對的？2023/3/4華南師范高校計(jì)算機(jī)學(xué)院562023/3/4華南師范高校計(jì)算機(jī)學(xué)院571.9空間困難性

S(n)＝space~。T(n)＝timecomplexity在上述意義下：S(n)可以對應(yīng)T(n)求法例1.17~1.21Page:20時(shí)間與空間的依存：權(quán)衡。時(shí)間，空間的反比關(guān)系。沖突，兌換一增一減存在限度。2023/3/4華南師范高校計(jì)算機(jī)學(xué)院581.10最優(yōu)算法閱讀，品一品Ｐ２０－２１兩段

排序算法中最優(yōu)的是？最優(yōu)算法的定義是？

舉出最優(yōu)排序算法的例子：BottomupsortBinarymergesort2023/3/4華南師范高校計(jì)算機(jī)學(xué)院591.11如何估計(jì)算法運(yùn)行時(shí)間

P21運(yùn)行時(shí)間常常和While循環(huán)及類似結(jié)構(gòu)的執(zhí)行次數(shù)成正比。比如：搜尋，排序，矩陣Ｐ２２例１.22Count1例１.23Count2例１.24Count3例１.25PSUMP23計(jì)算基本運(yùn)算的頻度：選個頻度最高或常數(shù)倍的元運(yùn)算作為評估時(shí)間的基本運(yùn)算P26運(yùn)用遞推關(guān)系，如T(n)=2T(n/2)+n2023/3/4華南師范高校計(jì)算機(jī)學(xué)院601.12最壞狀況和平均狀況的分析Theta不是總可以達(dá)到例1.29平均狀況，必需知道輸入出現(xiàn)的概率－－困難冗長例1.30,1.31

2023/3/4華南師范高校計(jì)算機(jī)學(xué)院611.13平攤分析情形：算法中有一種運(yùn)算反復(fù)執(zhí)行時(shí)，其運(yùn)行時(shí)間不停變動。該運(yùn)算大多數(shù)時(shí)候運(yùn)行快，少數(shù)狀況下費(fèi)時(shí)，同時(shí)假定求確界可能，但困難，引入平攤分析平攤分析中，算出算法在整個執(zhí)行中所需時(shí)間的平均值。稱該運(yùn)算的平攤運(yùn)行時(shí)間。Ｐ２９例1.322023/3/4華南師范高校計(jì)算機(jī)學(xué)院62留意到３０頁的第３段的分析４段的分析2023/3/4華南師范高校計(jì)算機(jī)學(xué)院631.14輸人大小和問題實(shí)例算法性能的測度通常是它輸入的大小、依次、分布等的函數(shù)。常用輸入大小的測度：Ｐ３１，５個情形排序，搜尋問題：數(shù)組或表中元素的數(shù)目圖的算法中：圖中的邊或頂點(diǎn)數(shù)目，或二者一起矩陣中：輸入矩陣的維數(shù)計(jì)算幾何中數(shù)論和密碼學(xué)中數(shù)學(xué)預(yù)備學(xué)問自學(xué)－其次章引導(dǎo)由于內(nèi)容和以前的專業(yè)基礎(chǔ)重復(fù)，默認(rèn)并信任大家具備須要的基礎(chǔ)如有不足，你怎么辦呢？2023/3/4華南師范高校計(jì)算機(jī)學(xué)院642023/3/4華南師范高校計(jì)算機(jī)學(xué)院65算法分析的數(shù)學(xué)準(zhǔn)備1.單調(diào)函數(shù)單調(diào)遞增：m

n

f(m)f(n);單調(diào)遞減：m

n

f(m)f(n);嚴(yán)格單調(diào)遞增：m

<n

f(m)<f(n);嚴(yán)格單調(diào)遞減：m

<n

f(m)>f(n).2.取整函數(shù)x：不大于x的最大整數(shù)；

x：不小于x的最小整數(shù)。2023/3/4華南師范高校計(jì)算機(jī)學(xué)院66取整函數(shù)的若干性質(zhì)：

x-1<xxx<x+1；

n/2

+n/2=n;

對于n

0，a,b>0，有：

n/a/b=n/ab;n/a/b=n/ab;a/b(a+(b-1))/b;a/b(a-(b-1))/b;

f(x)=x,g(x)=x為單調(diào)遞增函數(shù)。2023/3/4華南師范高校計(jì)算機(jī)學(xué)院673.