1、函數(shù)的漸進復(fù)雜性PPT課件1 函數(shù)的漸進復(fù)雜性PPT課件2 問題的模數(shù)（問題的模數(shù)（sizesize）用一個整數(shù)）用一個整數(shù)n n表示，它是表示，它是輸入數(shù)據(jù)的一個量度。輸入數(shù)據(jù)的一個量度。 例如，集合的運算，可以是集合的基數(shù)；例如，集合的運算，可以是集合的基數(shù)； 圖的運算，可以是圖的運算，可以是V V或或e e。 算 法 的 計 算 復(fù) 雜 性算 法 的 計 算 復(fù) 雜 性 （ c o m p l e x i t y o f c o m p l e x i t y o f computationcomputation）- - 是問題的模數(shù)的一個函數(shù)。是問題的模數(shù)的一個函數(shù)。函數(shù)的漸進復(fù)雜性P

2、PT課件3一個算法所需的機時，表示為一個算法所需的機時，表示為n n的函數(shù)，稱該算的函數(shù)，稱該算法的法的時間復(fù)雜性時間復(fù)雜性（time complexitytime complexity）。）。算法是程序的靈魂，程序的性能一般指程序算法是程序的靈魂，程序的性能一般指程序的空間復(fù)雜性和時間復(fù)雜性。的空間復(fù)雜性和時間復(fù)雜性。一個算法所需的存儲量，表示為一個算法所需的存儲量，表示為n n的函數(shù)，稱該的函數(shù)，稱該算法的算法的空間復(fù)雜性空間復(fù)雜性（space complexityspace complexity）。）。函數(shù)的漸進復(fù)雜性PPT課件4 函數(shù)的漸進復(fù)雜性PPT課件5函數(shù)的漸進復(fù)雜性PPT課件6

3、貨郎擔(dān)問題貨郎擔(dān)問題- - 貨郎擔(dān)問題貨郎擔(dān)問題 （公路調(diào)度）公路調(diào)度）貨郎擔(dān)問題貨郎擔(dān)問題函數(shù)的漸進復(fù)雜性PPT課件7貨郎擔(dān)問題貨郎擔(dān)問題 貨郎擔(dān)問題一般提法為：一個貨郎從貨郎擔(dān)問題一般提法為：一個貨郎從某城鎮(zhèn)出發(fā)，經(jīng)過若干個城鎮(zhèn)一次，且僅某城鎮(zhèn)出發(fā)，經(jīng)過若干個城鎮(zhèn)一次，且僅經(jīng)過一次，最后仍回到原出發(fā)的城鎮(zhèn)，問經(jīng)過一次，最后仍回到原出發(fā)的城鎮(zhèn)，問應(yīng)如何選擇行走路線可使總行程最短，這應(yīng)如何選擇行走路線可使總行程最短，這是運籌學(xué)的一個著名的問題。是運籌學(xué)的一個著名的問題。 實際中有很多問題可以歸結(jié)為這類問題。實際中有很多問題可以歸結(jié)為這類問題。函數(shù)的漸進復(fù)雜性PPT課件8實際中很多問題都可以歸結(jié)

4、為貨郎擔(dān)這實際中很多問題都可以歸結(jié)為貨郎擔(dān)這類問題。類問題。 如：如：1) 物資運輸路線中，汽車應(yīng)該走怎樣的路線物資運輸路線中，汽車應(yīng)該走怎樣的路線使路程最短；使路程最短；2) 工廠里在鋼板上要挖一些小圓孔，自動焊工廠里在鋼板上要挖一些小圓孔，自動焊接機的割咀應(yīng)走怎樣的路線使路程最短；接機的割咀應(yīng)走怎樣的路線使路程最短；3) 城市里有一些地方鋪設(shè)管道時，管子應(yīng)走城市里有一些地方鋪設(shè)管道時，管子應(yīng)走怎樣的路線才能使管子耗費最少，等等。怎樣的路線才能使管子耗費最少，等等。函數(shù)的漸進復(fù)雜性PPT課件9我們學(xué)的數(shù)據(jù)結(jié)構(gòu)里面也有很多我們學(xué)的數(shù)據(jù)結(jié)構(gòu)里面也有很多內(nèi)容和貨郎擔(dān)問題的思想相似內(nèi)容和貨郎擔(dān)問題的

5、思想相似!函數(shù)的漸進復(fù)雜性PPT課件10最小生成樹的普里姆算法最小生成樹的普里姆算法函數(shù)的漸進復(fù)雜性PPT課件11最短路徑問題最短路徑問題函數(shù)的漸進復(fù)雜性PPT課件12 三個城市三個城市，有，有2!2!個個“遍歷遍歷”路徑，每個路徑需路徑，每個路徑需做做2 2次加法，一次比較運算。共有次加法，一次比較運算。共有3 32 2！運算。！運算。- - 有有2!2!個個“遍歷遍歷”路徑路徑 貨郎擔(dān)問題貨郎擔(dān)問題函數(shù)的漸進復(fù)雜性PPT課件13 四個城市四個城市，有，有3!3!個個“遍歷遍歷”路徑，每個路徑路徑，每個路徑需做需做3 3次加法次加法, ,一次比較運算。共有一次比較運算。共有4 43 3！運算

6、。！運算。 - - 有有3!3!個個“遍歷遍歷”路徑路徑 函數(shù)的漸進復(fù)雜性PPT課件14 n n個城市個城市，有（，有（n-1n-1）! !個個“遍歷遍歷”路徑，每個路徑路徑，每個路徑 需做需做(n-1)(n-1)次加法次加法, ,一次比較運算。一次比較運算。 共有共有n n(n-1)(n-1)！=n!=n!運算。運算。按上述算法，搜索最短路徑需要的按上述算法，搜索最短路徑需要的 時間復(fù)雜性為：時間復(fù)雜性為：f(n)=cf(n)=c* *n!n! 空間復(fù)雜性為空間復(fù)雜性為n n2 2（n n個邊的相鄰矩陣）。個邊的相鄰矩陣）。顯然，時間復(fù)雜性顯然，時間復(fù)雜性 n! n! 是個是個explosi

7、veexplosive問題。問題。函數(shù)的漸進復(fù)雜性PPT課件15 例如例如，若有，若有5656個點：個點： 有有5656個點需做加法：個點需做加法： 5656！7.17.110107474次次 一年秒數(shù)：一年秒數(shù)： 6060秒秒6060分分2424小時小時365365天天3.153.1510107 7秒秒 每秒每秒1010億次計算機億次計算機10109 9次次/ /秒秒 5656！7.17.110107474次加法所需時間：次加法所需時間： 21063 小時 8.21061 天 2.251059 年函數(shù)的漸進復(fù)雜性PPT課件16由此可見，貨郎擔(dān)問題的時間復(fù)雜性是：由此可見，貨郎擔(dān)問題的時間復(fù)雜

8、性是： f(n)=cn!f(n)=cn!由以上的條件可知：由以上的條件可知： n n的函數(shù)是的函數(shù)是N N R R+ +（正實數(shù)）的一個映射。（正實數(shù)）的一個映射。即，即， 當(dāng)當(dāng)n n是是N N中的元時（中的元時（nnN N），），f(n)=cn!f(n)=cn!R R+ +函數(shù)的漸進復(fù)雜性PPT課件17課后思考題？課后思考題？ 中國有中國有34個一級城市，采用窮舉法求個一級城市，采用窮舉法求連通各個一級城市的最短路徑長度，連通各個一級城市的最短路徑長度，能計算出來嗎？理論上計算需要多少能計算出來嗎？理論上計算需要多少年？年？ 請思考：采用哪些近似算法可以得到請思考：采用哪些近似算法可以得到滿

9、意解？滿意解？函數(shù)的漸進復(fù)雜性PPT課件18 函數(shù)的漸進復(fù)雜性PPT課件19 確定程序的操作計數(shù)和執(zhí)行步數(shù)的目的：確定程序的操作計數(shù)和執(zhí)行步數(shù)的目的：為了比較兩個完成同一功能的程序的時間復(fù)雜性，預(yù)測程序的運行時間隨著實例特征變化的變化量。 設(shè) 是算法A的復(fù)雜性函數(shù)。一般說來，當(dāng)n單調(diào)增加趨于時， 也將單調(diào)增加趨于。)(nT)(nT 如果存在函數(shù)如果存在函數(shù) ，使得當(dāng)，使得當(dāng) 時有時有 ，則稱，則稱 是是 當(dāng)當(dāng) 時的時的漸近性態(tài)漸近性態(tài)，或稱，或稱 是算法是算法A當(dāng)當(dāng) 的的漸漸近復(fù)雜性。近復(fù)雜性。 )(nTn0)()()(nTnTnT)(nT)(nTn)(nTn函數(shù)的漸進復(fù)雜性PPT課件20定義

10、定義1.2.11.2.1：漸進控制漸進控制 設(shè)有設(shè)有 N N 到到 R R+ +( (正實數(shù)）正實數(shù)）的映射的映射f f和和g g， 那么那么g g漸進控制漸進控制f,f, 若存在常數(shù)若存在常數(shù)m m，使，使 f(n)mg(n),f(n)mg(n), for all nk, k0 for all nk, k0 即從某一個值即從某一個值k k開始，開始，g g乘以一固定常數(shù)乘以一固定常數(shù)m m 之后，總大于之后，總大于f f。 函數(shù)的漸進復(fù)雜性PPT課件21例例1.1. 設(shè)設(shè)f=3n-1, g=nf=3n-1, g=n2 2, n, nN N 當(dāng)當(dāng)m=1,k=3m=1,k=3時，時， fmg f

11、mg ( (在在n=3n=3之后，總是之后，總是gf)gf) g g漸進控制漸進控制f f。函數(shù)的漸進復(fù)雜性PPT課件22例例2 2: : 設(shè)設(shè)f=cn, g=nf=cn, g=n fcg, fcg, 而而g( )g( )* *f, for all nf, for all nN N f f與與g g是相互漸進的控制。是相互漸進的控制。c1函數(shù)的漸進復(fù)雜性PPT課件23定理定理1.2.11.2.1: : 設(shè)設(shè)F F是是N N到到R R+ +（正實數(shù)）（正實數(shù)）函數(shù)的集合，那么，函數(shù)的集合，那么， F F的的二元關(guān)系二元關(guān)系“漸進控制漸進控制”自反和可遷。自反和可遷。 F F的的二元關(guān)系二元關(guān)系“

12、相互漸進控制相互漸進控制”是是F F的一個等價關(guān)的一個等價關(guān)系（自反、可遷、對稱）。系（自反、可遷、對稱）。注：注：. .自反：自反：- - 若對每個若對每個xAxA，xRxxRx，那么，那么R R自反。自反。 . .可遷：可遷：- xRyyRz xRz- xRyyRz xRz，那么，那么，R R可遷。可遷。 . .對稱：對稱：- - 若對每個若對每個x,yAx,yA，xRy yRxxRy yRx，那么，那么R R對稱。對稱。 注：注：A A為某種關(guān)系的集合。為某種關(guān)系的集合。函數(shù)的漸進復(fù)雜性PPT課件24定義定義1.2.21.2.2： g g漸進控制的所有函數(shù)集合，用漸進控制的所有函數(shù)集合，

13、用O(g)O(g)表示，稱表示，稱OrderOrder g g 或或 O(g)O(g)。 若若fO(g)fO(g)， 那么稱那么稱f f是是O(g)O(g)。 函數(shù)的漸進復(fù)雜性PPT課件25定理定理1.2.21.2.2： g是O(g) 若f是O(g)，那么cf也是O(g) 若f和h是O(g)，那么f+h也是O(g) 證證： 設(shè) fm1g for nk1 hm2g for nk2 那么，f+h(m1+m2)g for nmax(k1,k2)推理推理： 多項式a0 + a1n + a2n2+ + arnr 是 O(nr). 函數(shù)的漸進復(fù)雜性PPT課件26例例3 3， 2n2+3n+4 nncrlo

14、glog n2漸進控制4、3n和2n2， 按定理1.2.2 , 2n2+3n+4 是 O(n2). 函數(shù)的漸進復(fù)雜性PPT課件27 f f是是O(g),iffO(g),iff（如果且只要是）（如果且只要是）O(f)O(g).O(f)O(g).推理： f f是是O(g)O(g)，g g是是O(f)O(f)，iff O(f)=O(g)iff O(f)=O(g)這個推理和定理一樣重要，舉一簡單例子， cn2是O(n2), n2是O(cn2), O(cn2)=O(n2) f=an2+bn+c 是O(n2), n2是O(f), O(f)=O(n2) 函數(shù)的漸進復(fù)雜性PPT課件28定義定義1.2.31.2

15、.3： 漸進復(fù)雜性漸進復(fù)雜性 asymptotic complexityasymptotic complexity 設(shè)算法的復(fù)雜性函數(shù)是f，那么O(f)叫做該算法的漸進復(fù)雜性漸進復(fù)雜性。例例4,4, f=an f=an2 2+bn+c, +bn+c, 那么該算法漸進復(fù)雜性是那么該算法漸進復(fù)雜性是O(f),O(f),即即O(nO(n2 2) )。 g=bn+cg=bn+c的漸進復(fù)雜性是的漸進復(fù)雜性是O(g),O(g),即即O(n)O(n)。 函數(shù)的漸進復(fù)雜性PPT課件29漸進復(fù)雜性的幾個重要的類：漸進復(fù)雜性的幾個重要的類： O(1) f=c O(1) f=c 是是 O(c)=O(1) O(c)=

16、O(1) 常數(shù)復(fù)雜性常數(shù)復(fù)雜性 O(logn) f=logn,logO(logn) f=logn,log1010n=lognn=lognlg10 lg10 對數(shù)復(fù)雜性對數(shù)復(fù)雜性 O(n) O(n) 線性復(fù)雜性線性復(fù)雜性 O(nlogn) O(nlogn) 線性對數(shù)乘積復(fù)雜性線性對數(shù)乘積復(fù)雜性 O(n O(n2 2) ) 平方復(fù)雜性平方復(fù)雜性 O(nO(n3 3) ) 立方復(fù)雜性立方復(fù)雜性 O(cO(cn n) ) 指數(shù)復(fù)雜性指數(shù)復(fù)雜性 O(n!) O(n!) 階乘復(fù)雜性階乘復(fù)雜性 后面一個包含前面一個（一個比一個高階）：后面一個包含前面一個（一個比一個高階）： O(1)O(logn)O(n)O

17、(nlogn)O(n2)O(n3)O(cn)O(n!)函數(shù)的漸進復(fù)雜性PPT課件30證證: : O(nr)O(cn) nrcn 如果 rlognnlogc 但 是增函數(shù)，（r不是n的函數(shù)）， 不等式在nk后成立。 n nr rccn n 即， nr是O(cn), 而cn不是O(nr) O(nr)O(cn)nnlog函數(shù)的漸進復(fù)雜性PPT課件31n n1 1 0 01 1 0 02 21 1 0 03 31 1 0 04 41 1 0 05 5l l o o g g n n n n n n l l o o g g n n3 3 . . 3 3 1 1 0 03 3 . . 3 36 6 . .

18、6 61 1 0 01 1 3 3 . . 3 31 1 6 6 . . 6 61 1 0 01 1 0 02 21 1 0 03 31 1 0 04 41 1 0 05 56 6 . . 6 6 1 1 0 02 21 1 0 0 1 1 0 03 31 1 3 3 . . 3 3 1 1 0 04 41 1 6 6 . . 6 6 1 1 0 05 5n n2 21 1 0 04 41 1 0 06 61 1 0 08 81 1 0 01 1 0 01 1 0 02 21 1 0 06 61 1 0 09 9- -1 1 0 01 1 5 51 1 0 03 3n n3 32 2n n1

19、1 0 0 2 2 4 41 1 . . 3 3 1 1 0 03 3 0 01 1 . . 1 1 1 1 0 03 3 0 0 1 1- -n n ! !3 3 . . 6 6 1 1 0 06 69 9 . . 2 2 1 1 0 01 1 5 5 7 7- - - -v衡量衡量兩個算兩個算法的好法的好壞，應(yīng)壞，應(yīng)當(dāng)是在當(dāng)是在n足夠足夠大大的情的情形下，形下，對算法對算法的工作的工作量進行量進行比較。比較。函數(shù)的漸進復(fù)雜性PPT課件32函數(shù)增長表函數(shù)增長表： )(nTv一般情況下，隨著一般情況下，隨著n的增大，增長較慢的算法為的增大，增長較慢的算法為最優(yōu)的算法最優(yōu)的算法。v應(yīng)該選擇對數(shù)階

20、或多項式階的算法，避免使用指數(shù)階的算法。應(yīng)該選擇對數(shù)階或多項式階的算法，避免使用指數(shù)階的算法。函數(shù)的漸進復(fù)雜性PPT課件33 進一步分析可知，要比較兩個算法的漸近復(fù)雜性進一步分析可知，要比較兩個算法的漸近復(fù)雜性的階不相同時，只要確定出各自的的階不相同時，只要確定出各自的階階，就可以知，就可以知道哪一個算法的效率高。道哪一個算法的效率高。 換句話說，換句話說，漸近復(fù)雜性分析只要關(guān)心漸近復(fù)雜性分析只要關(guān)心 的階的階就就夠了，不必關(guān)心包含在夠了，不必關(guān)心包含在 中的常數(shù)因子。中的常數(shù)因子。 所以，我們常常可對所以，我們常常可對 的分析進一步簡化，即的分析進一步簡化，即假設(shè)算法中用到的所有不同的運算（

21、基本）各執(zhí)假設(shè)算法中用到的所有不同的運算（基本）各執(zhí)行一次所需要的時間都是一個單位時間。行一次所需要的時間都是一個單位時間。 )()(limngnfn)()(limngnfn)()(limngnfn函數(shù)的漸進復(fù)雜性PPT課件34 - 求解函數(shù)的上界求解函數(shù)的上界“ ”，下界下界“ ”，同階同階“ ”函數(shù)的漸進復(fù)雜性PPT課件35 根據(jù)以上分析，我們已經(jīng)給出了簡化算法復(fù)雜性根據(jù)以上分析，我們已經(jīng)給出了簡化算法復(fù)雜性分析的方法和步驟，即只考慮當(dāng)分析的方法和步驟，即只考慮當(dāng)問題的規(guī)模問題的規(guī)模充分充分大大時，時，算法復(fù)雜性在漸近意義下的階算法復(fù)雜性在漸近意義下的階。 為此引入漸近符號，首先給出常用的

22、漸近函數(shù)。為此引入漸近符號，首先給出常用的漸近函數(shù)。 在下面的討論中，用在下面的討論中，用f(n)表示一個程序的時間表示一個程序的時間或空間復(fù)雜性，它是實例特征或空間復(fù)雜性，它是實例特征n（一般是輸入規(guī)模）（一般是輸入規(guī)模）的函數(shù)。由于一個程序的時間或空間需求是一個的函數(shù)。由于一個程序的時間或空間需求是一個非負的實數(shù)，我們假定非負的實數(shù)，我們假定函數(shù)函數(shù)f(n)對于對于n的所有取值的所有取值均為非負實數(shù)均為非負實數(shù)，而且還可假定，而且還可假定n0。 函數(shù)的漸進復(fù)雜性PPT課件36 f(n)=O(g(n) 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)存在正的常數(shù)存在正的常數(shù)c和和n0，使得對于所有的使得對于所有的nn0，有

23、，有f(n)cg(n)。 此時，稱此時，稱g(n)是是f(n)的一個的一個上界上界。 f(n)的階的階小于或等于小于或等于g(n)的階的階函數(shù)的漸進復(fù)雜性PPT課件37 即是說，當(dāng)即是說，當(dāng)n充分大時，充分大時，g是是 f 的一個上界函的一個上界函數(shù)，在相差一個非零常數(shù)倍的情況下。數(shù)，在相差一個非零常數(shù)倍的情況下。有有 f(n)cg(n) 2=O(n): 可取可取 c1，n02 100n+6=O(n): 可取可取 c=101，n06 62n+n2=O(2n): 可取可取 c =7，n0=4函數(shù)的漸進復(fù)雜性PPT課件38 用來作比較的函數(shù)用來作比較的函數(shù)g(n)g(n)應(yīng)該盡量接近所考慮應(yīng)該盡量

24、接近所考慮 的函數(shù)的函數(shù)f(n)f(n)。 例如，例如，3n+2=O(n2) 松散的界限； 3n+2=O(n) 較好的界限。 不要產(chǎn)生錯誤界限。不要產(chǎn)生錯誤界限。 例如，例如，n2+100n+6，當(dāng)n3時，n2+100n+6c-100就有n2+100n+6 cn. 同理，3n2+42n=O(n2)是錯誤的界限。 函數(shù)的漸進復(fù)雜性PPT課件39 f(n)=O(g(n)f(n)=O(g(n)不能寫成不能寫成g(n)=O(f(n)g(n)=O(f(n)，因為，因為 兩者并不等價。兩者并不等價。 實際上，這里的等號并不是通常相等的含義。 按照定義，用集合符號集合符號更準(zhǔn)確些： O(g(n)=f(n)|

25、O(g(n)=f(n)|f(n)f(n)滿足：存在正的常數(shù)滿足：存在正的常數(shù)c c和和n n0 0， 使得當(dāng)使得當(dāng)nnnn0 0時，時，f(n)cg(n)f(n)cg(n) 所以，人們常常把f(n)=O(g(n)讀作： “”， 或者 “”。 函數(shù)的漸進復(fù)雜性PPT課件40 對于函數(shù)對于函數(shù)f(n)和和g(n)，如果極限，如果極限 存在，存在， 則則 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)存在存在正的常數(shù)正的常數(shù)c，使得，使得 . )( () (ngOn f cngnfn)()(lim622*6lim2nnnn函數(shù)的漸進復(fù)雜性PPT課件41因為因為 ， 所以所以 ；因為因為 ，所以，所以 ；因為因為 ，所以，所以 ；

26、因為因為 ，所以，所以 ， )2 (2*62nnOn02*3lim216nnnn)2 (*3216nOnn102410lim22nnnn)(241022nOnn323limnnn)(23nOn xxnn)(log)(log- - 但是，最后的一個例子并不是一個好的上界估但是，最后的一個例子并不是一個好的上界估計，問題出在極限值不是正的常數(shù)。計，問題出在極限值不是正的常數(shù)。函數(shù)的漸進復(fù)雜性PPT課件42對于任意一個對于任意一個正正實數(shù)實數(shù)x x和和，有下面的不等式：，有下面的不等式：存在某個存在某個n0使得對于任何使得對于任何nn0 ，有，有存在某個存在某個n0使得對于任何使得對于任何nn0 ，

27、有，有下述不等式對于復(fù)雜性下述不等式對于復(fù)雜性階的估算階的估算非常有幫助：非常有幫助： nnx)(logxxnn函數(shù)的漸進復(fù)雜性PPT課件43存在某個存在某個n0使得對于任何使得對于任何nn0 ， 有有 .存在某個存在某個n0使得對于任何使得對于任何nn0 ， 有有 .對任意對任意實數(shù)實數(shù)y，存在某個，存在某個n0使得對于任何使得對于任何 nn0 ，有，有 .nxn2xyxnnn)(log)(log323nOnnn函數(shù)的漸進復(fù)雜性PPT課件44 根據(jù)漸進控制的定義，我們很容易得出：根據(jù)漸進控制的定義，我們很容易得出： )(log4205 . 24nOnnn)log/2 (log/2log235

28、3534nnOnnnnnnn)(/)(limnfngn 函數(shù)的漸進復(fù)雜性PPT課件45 f(n)=(g(n)當(dāng)且僅當(dāng)存在正的常數(shù)當(dāng)且僅當(dāng)存在正的常數(shù)c和和n0，使得對于所有的使得對于所有的nn0，有，有f(n)c(g(n)。 此此時，稱時，稱g(n)是是f(n)的一個的一個下界下界。 f(n)的階的階大于或等于大于或等于g(n)的階的階函數(shù)的漸進復(fù)雜性PPT課件46當(dāng)當(dāng)n充分大時，充分大時，g是是f的一個下界函數(shù)，在的一個下界函數(shù)，在相差一個非零常數(shù)倍的情況下。類似于大相差一個非零常數(shù)倍的情況下。類似于大O符號，我符號，我們可以參考定理們可以參考定理1.2.4.所列的不等式，來估計復(fù)雜性所列的

29、不等式，來估計復(fù)雜性函數(shù)的下界，而且有下述判定規(guī)則：函數(shù)的下界，而且有下述判定規(guī)則： 對于函數(shù)對于函數(shù)f(n)和和g(n)，如果極限，如果極限 存在，存在，則則 當(dāng)且僅當(dāng)存在當(dāng)且僅當(dāng)存在正的常數(shù)正的常數(shù)c，使得，使得 . 這里，當(dāng)這里，當(dāng)n充分大時，充分大時，g(n)cf(n)意味著意味著 ，由，由此不難看出上述判別規(guī)則的正確性。此不難看出上述判別規(guī)則的正確性。)()(ngnfcnfngn)()(lim )(1)(ngcnf)( () ()( (21n gcn fn gc函數(shù)的漸進復(fù)雜性PPT課件47 f(n)=(g(n)當(dāng)且僅當(dāng)存在正的常數(shù)當(dāng)且僅當(dāng)存在正的常數(shù)C1，C2和和n0，使得對于所有

30、的，使得對于所有的nn0，有，有 此時，稱此時，稱f(n)與與g(n)同階同階。 )(23nn函數(shù)的漸進復(fù)雜性PPT課件48 )(241022nnn)2(252nnn)(/)(limngnfn 函數(shù)的漸進復(fù)雜性PPT課件49 對于函數(shù)對于函數(shù)f(n)f(n)和和g(n)g(n)，如果極限，如果極限 與與 都存在，則都存在，則f(n)=(g(n)f(n)=(g(n)當(dāng)且僅當(dāng)且僅當(dāng)當(dāng)存在正的常數(shù)存在正的常數(shù)C C1 1和和C C2 2，使得，使得 )(/ )(limnfngn2)()(limcnfngn ,)()(lim1cngnfn0111an anan ammmm函數(shù)的漸進復(fù)雜性PPT課件50

31、對于多項式函數(shù)對于多項式函數(shù) ，如果如果am0 ，則，則 ， ， . . 比較大比較大O O比率定理和比率定理和比率定理，可知，比率定理，可知，比率定比率定理實際是那兩種情況的綜合。對于多項式情形的復(fù)雜理實際是那兩種情況的綜合。對于多項式情形的復(fù)雜性函數(shù)，其階函數(shù)可取該多項式的最高項，性函數(shù)，其階函數(shù)可取該多項式的最高項，)()(mnOnf)()(mnnf)()(mnnf)(lognO函數(shù)的漸進復(fù)雜性PPT課件51 一般情況下，我們不能對每個復(fù)雜性函數(shù)去一般情況下，我們不能對每個復(fù)雜性函數(shù)去估計它們的上界、下界和估計它們的上界、下界和“雙界雙界”。前面介紹。前面介紹的定理給了一些直接確定這些界

32、的階函數(shù)（或的定理給了一些直接確定這些界的階函數(shù)（或叫漸近函數(shù)）的參考信息。由這些信息可以給叫漸近函數(shù)）的參考信息。由這些信息可以給出多個函數(shù)經(jīng)過加、乘運算組合起來的復(fù)雜函出多個函數(shù)經(jīng)過加、乘運算組合起來的復(fù)雜函數(shù)的階的估計。數(shù)的階的估計。 函數(shù)的漸進復(fù)雜性PPT課件52算法的階算法的階小結(jié)小結(jié) 一般采用一般采用求極限的方法求極限的方法，來比較兩個算法時間復(fù)雜，來比較兩個算法時間復(fù)雜性函數(shù)的階：性函數(shù)的階： 當(dāng)當(dāng)n時，時，lim f(n)/g(n)=c (1)當(dāng)當(dāng)c0，f(n)比比g(n)低階，記為低階，記為f(n) = O(g(n)； (2)當(dāng)當(dāng)c0，f(n)和和g(n)同階，記為同階，記為

33、f(n) =(g(n)； (3)當(dāng)當(dāng)c，f(n)比比g(n)高階，記為高階，記為f(n) =(g(n)； 函數(shù)的漸進復(fù)雜性PPT課件53算法的階算法的階寫法寫法條件假設(shè)條件假設(shè)近似近似f = O(g)nn0 , f(n)cg(n)f =(g)f = O(g) and g = O(f)f =(g)g = O(f)上界上界“ ”，下界下界“ ”，同階同階“ ”函數(shù)的漸進復(fù)雜性PPT課件54例例 題題 例如：例如：2n-5 = O(n2)，因為當(dāng)，因為當(dāng)n時，時，lim (2n -5)/n2 = 2/n - 5/n2 0-0=0；-低階低階 例如：例如：5n2 -3n=(n2)，因為當(dāng)，因為當(dāng)n時，

34、時，lim (5n2 -3n)/n2 = 5 - 3/n5-0=5；-同階同階 例如：例如： n2 +5n=(n)，因為當(dāng)，因為當(dāng)n時，時，lim (n2 +5n)/n= n +5 ；-高階高階函數(shù)的漸進復(fù)雜性PPT課件55最后最后給出給出折半折半搜索搜索程序程序及算及算法復(fù)法復(fù)雜性雜性估計：估計： template int BinarySearch (T a , const T &x, int n) /在在a0=a1=an-1中搜索中搜索x /如果找到，則返回所在位置，否則返回如果找到，則返回所在位置，否則返回 1 int left=0; int right =n-1; while

35、( leftamiddle) left = middle+1; else right = middle 1; return 1; /未找到未找到x x 函數(shù)的漸進復(fù)雜性PPT課件56例：例：有有11個數(shù)據(jù)元素的順序表個數(shù)據(jù)元素的順序表 （05，13，19，21，37，56，64，75，80，88，92） 序號：序號： 1 2 3 4 5 6 7 8 9 10 11 折半查找法在查找成功時進行比較的關(guān)鍵字個數(shù)最多不超折半查找法在查找成功時進行比較的關(guān)鍵字個數(shù)最多不超過過判定樹判定樹的深度的深度，而具有而具有n個結(jié)點的判定樹的深度為個結(jié)點的判定樹的深度為 logn +1，所以折半查找法在查找成功時

36、和給定值進行比，所以折半查找法在查找成功時和給定值進行比較的關(guān)鍵字個數(shù)至多為較的關(guān)鍵字個數(shù)至多為 logn +1 。6312457891011函數(shù)的漸進復(fù)雜性PPT課件57 while while 的每次循環(huán)（最后一次除外）都將以減半的比例縮小搜索范圍，所以，該循環(huán)在最壞的情況下需要執(zhí)行 次。 由于每次循環(huán)需耗時 ，因此在最壞情況下，總的時間復(fù)雜性為時間復(fù)雜性為 。)1(O)(log nO 1 nif (n) )2n2T(T(n)1 nif ) 1 ()()(nTnT函數(shù)的漸進復(fù)雜性PPT課件58 函數(shù)的漸進復(fù)雜性PPT課件59 遞歸方程是使用小的輸入值來描述一個函數(shù)的方程或不等式。Merge

37、-sort 排序算法的復(fù)雜性方程排序算法的復(fù)雜性方程: : T(n) 的解是的解是(nlogn).TnTnn() 22函數(shù)的漸進復(fù)雜性PPT課件60 1. Substitution（猜解替代）（猜解替代）: Guess first，然后用數(shù)學(xué)歸納法證明。，然后用數(shù)學(xué)歸納法證明。2. Iteration（循環(huán)遞歸）（循環(huán)遞歸）: 把方程轉(zhuǎn)化為一個和式，然后用和估計技術(shù)求解。把方程轉(zhuǎn)化為一個和式，然后用和估計技術(shù)求解。函數(shù)的漸進復(fù)雜性PPT課件61（猜解替代）一般方法一般方法: : 猜解的形式猜解的形式 用數(shù)學(xué)歸納法證明猜測的解正確用數(shù)學(xué)歸納法證明猜測的解正確 - 該方法只能用于解可猜的情況該方法

38、只能用于解可猜的情況。函數(shù)的漸進復(fù)雜性PPT課件62 無一般的猜測正確解的方法，需要 經(jīng)驗 機會 創(chuàng)造性和靈感 存在一些啟發(fā)規(guī)則幫助人們?nèi)ゲ聹y。函數(shù)的漸進復(fù)雜性PPT課件63 求解 , T(1)=1. 1212) 1( mmTmT展開展開T(T(n n) )若干步若干步, ,可以猜測可以猜測 T( T(n n)=)=O O( (n nloglogn n).).我們需要證明我們需要證明T(T(n n)=)=O O( (n nloglogn n). ). 函數(shù)的漸進復(fù)雜性PPT課件641.當(dāng)nm時都成立. 2.則當(dāng) n=m+1時 有： 于是有，于是有， . 121log212mmmC C mmm( )(lg ( ) )11 11)1)(1()1lg()1(CmmmC)1lg()1(mmC)log()(nnOnT （只要（只要C1） 2log24222222) 2(CTT用數(shù)用數(shù)學(xué)歸學(xué)歸納法納法證明證明猜測猜測的解的解正確正確函數(shù)的漸進復(fù)雜性PPT課件65nnTnT1722)(只需只需C C 2 2，這與上頁的，這與上頁的C1C1不矛盾。不矛盾。函數(shù)的漸進復(fù)雜性PPT課件66求解 TnTn2172與只相差一個只相差一個17. 17. 猜測猜測: : TnTn2172與1212) 1( mmTmT與與當(dāng)當(dāng)n n充分大時充分大時 的差別并不大。的差別并不大。 nn21 72與