第 2 章 算法效率分析課件.ppt

《第 2 章 算法效率分析課件.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第二章算法效率分析算法效率（Efficiency）算法效率有什么作用算法效率是怎樣度量的，評(píng)價(jià)算法優(yōu)劣的依據(jù)是什么怎樣完成算法算法效率分析算法的復(fù)雜性算法的復(fù)雜性是算法效率的度量，是評(píng)價(jià)算法優(yōu)劣的重要依據(jù)。一個(gè)算法的復(fù)雜性的高低體現(xiàn)在運(yùn)行該算法所需要的計(jì)算機(jī)資源的多少上面，所需的資源越多，我們就說該算法的復(fù)雜性越高；反之，所需的資源越低，則該算法的復(fù)雜性越低。計(jì)算機(jī)的資源，最重要的是時(shí)間和空間（即存儲(chǔ)器）資源。因而，算法的復(fù)雜性有時(shí)間復(fù)雜性和空間復(fù)雜性之分。算法效率有什么作用不言而喻，對(duì)于任意給

2、定的問題，設(shè)計(jì)出復(fù)雜性盡可能低的算法是我們?cè)谠O(shè)計(jì)算法的一個(gè)重要目標(biāo)；另一方面，當(dāng)給定的問題已有多種算法時(shí)，選擇其中復(fù)雜性最低者，是我們?cè)谶x用算法應(yīng)遵循的一個(gè)重要準(zhǔn)則。因此，算法的復(fù)雜性分析對(duì)算法的設(shè)計(jì)或選用有著重要的指導(dǎo)意義和實(shí)用價(jià)值。問題怎樣完成算法算法效率分析？用怎樣的一個(gè)量來表達(dá)一個(gè)算法的復(fù)雜性；對(duì)于給定的一個(gè)算法，怎樣具體計(jì)算它的復(fù)雜性。復(fù)雜性的計(jì)量（一）算法的復(fù)雜性是算法運(yùn)行所需要的計(jì)算機(jī)資源的量，需要的時(shí)間資源的量稱作時(shí)間復(fù)雜性，需要的空間（即存儲(chǔ)器）資源的量稱作空間復(fù)雜性。這個(gè)量應(yīng)

3、該集中反映算法中所采用的方法的效率，而從運(yùn)行該算法的實(shí)際計(jì)算機(jī)中抽象出來。換句話說，這個(gè)量應(yīng)該是只依賴于算法要解的問題的規(guī)模、算法的輸入和算法本身的函數(shù)。如果分別用N、I和A來表示算法要解問題的規(guī)模、算法的輸入和算法本身，用C表示算法的復(fù)雜性，那么應(yīng)該有：C=F(N,I,A)復(fù)雜性的計(jì)量（二）其中F(N,I,A)是N,I,A的一個(gè)確定的三元函數(shù)。如果把時(shí)間復(fù)雜性和空間復(fù)雜性分開，并分別用T和S來表示，那么應(yīng)該有：T=T(N,I,A)(2.1.1)和S=S(N,I,A)(2.1.2)通常，我們讓A

4、隱含在復(fù)雜性函數(shù)名當(dāng)中，因而將（2.1.1）和（2.1.2）分別簡(jiǎn)寫為：T=T(N,I)和S=S(N,I)。由于時(shí)間復(fù)雜性和空間復(fù)雜性概念類同，計(jì)算方法相似，且空間復(fù)雜性分析相對(duì)地簡(jiǎn)單些，所以將主要地討論時(shí)間復(fù)雜性。復(fù)雜性的計(jì)量（三）根據(jù)T(N,I)的概念，它應(yīng)是算法在一臺(tái)抽象計(jì)算機(jī)上運(yùn)行所需的時(shí)間。設(shè)此抽象計(jì)算機(jī)所提供的元運(yùn)算有k種，記為O1，O2，...，Ok；再設(shè)這些元運(yùn)算每執(zhí)行一次所需要的時(shí)間分別為t1，t2，...，tk。對(duì)于給定的算法A，設(shè)經(jīng)過統(tǒng)計(jì)，用到元運(yùn)算Oi的次數(shù)分別為ei，i

5、=1，2，...，k，很明顯，對(duì)每一個(gè)i，1<=i<=k，ei是N和I的函數(shù)，即ei=ei(N,I)。那么有：T(N,I)=∑tiei(N,I)(2.1.3)其中{ti

6、i=1,2,..,k},是與N,I無關(guān)的常數(shù)。復(fù)雜性的計(jì)量（四）下面只考慮三種情況的復(fù)雜性，即最壞情況、最好情況和平均情況下的時(shí)間復(fù)雜性，并分別記為Tmax(N)、Tmin(N)和Tavg(N)。在數(shù)學(xué)上有：其中，DN是規(guī)模為N的合法輸入的集合；I*是DN中一個(gè)使T(N,I*)達(dá)到Tmax(N)的合法輸入，I~是DN中一個(gè)使T(

7、N,I~)到Tmin(N)的合法輸入；而P(I)是在算法的應(yīng)用中出現(xiàn)輸入I的概率。復(fù)雜性的計(jì)量（五）以上三種情況下的時(shí)間復(fù)雜性各從某一個(gè)角度來反映算法的效率，各有各的用處，也各有各的局限性。但實(shí)踐表明可操作性最好的且最有實(shí)際價(jià)值的是最壞情況下的時(shí)間復(fù)雜性。一般來說，最好情況和最壞情況的時(shí)間復(fù)雜性是很難計(jì)量的，原因是對(duì)于問題的任意確定的規(guī)模N達(dá)到了Tmax(N)的合法輸入難以確定，而規(guī)模N的每一個(gè)輸入的概率也難以預(yù)測(cè)或確定。我們有時(shí)也按平均情況計(jì)量時(shí)間復(fù)雜性，但那時(shí)在對(duì)P(I)做了一些人為的假設(shè)（

8、比如等概率）之后才進(jìn)行的。所做的假設(shè)是否符合實(shí)際總是缺乏根據(jù)。因此，在最好情況和平均情況下的時(shí)間復(fù)雜性分析還僅僅是停留在理論上。復(fù)雜性的漸近性（一）隨著經(jīng)濟(jì)的發(fā)展、社會(huì)的進(jìn)步、科學(xué)研究的深入，要求用計(jì)算機(jī)解決的問題越來越復(fù)雜，規(guī)模越來越大。但是，如果對(duì)這類問題的算法進(jìn)行分析時(shí)，把所有的元運(yùn)算都考慮進(jìn)去，精打細(xì)算，那么，由于問題的規(guī)模很大且結(jié)構(gòu)復(fù)雜，算法分析的工作量之大、步驟之繁將令人難以承受。因此，人們提出了對(duì)于規(guī)模充分大、結(jié)構(gòu)又十分復(fù)雜的問題的求解算法，其復(fù)雜性分析應(yīng)如何簡(jiǎn)化的問題。復(fù)雜性的漸

9、近性（二）設(shè)T(N)是在第二段中所定義的關(guān)于算法A的復(fù)雜性函數(shù)。一般說來，當(dāng)N單調(diào)增加且趨于∞時(shí),T(N)也將單調(diào)增加趨于∞。對(duì)于T(N)，如果存在T’(N)，使得當(dāng)N→∞時(shí)有：(T(N)-T’(N))/T(N)→0我們就說T’(N)是T(N)當(dāng)N→∞時(shí)的漸近性態(tài)，或叫T’(N)為算法A當(dāng)N→∞的漸近復(fù)雜性而與T(N)相區(qū)別，因?yàn)樵跀?shù)學(xué)上，T’(N)是T(N)當(dāng)N→∞時(shí)的漸近表達(dá)式。T’(N)是T(N)中略去低階項(xiàng)所留下的主項(xiàng)。所以它無疑比T(N)來得簡(jiǎn)單。比如當(dāng)T(N)=3N2+4Nlog2N