算法效率分析與分治法的應(yīng)用

《算法效率分析與分治法的應(yīng)用》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、算法效率與分治算法的應(yīng)用長沙市一中曹利國算法效率的評(píng)價(jià)算法的評(píng)估有時(shí)求解同一個(gè)問題常常有多種可用的算法，在一定的條件下當(dāng)然要選擇使用好的算法。用什么方法評(píng)估算法的好壞呢？通常使用算法復(fù)雜性這一概念來評(píng)估算法。算法評(píng)價(jià)算法執(zhí)行時(shí)間需通過依據(jù)該算法編制的程序在計(jì)算機(jī)上運(yùn)行時(shí)所消耗的時(shí)間來度量。而度量一個(gè)程序的執(zhí)行時(shí)間通常有兩種方法：事后統(tǒng)計(jì)的方法事前分析估算的方法算法評(píng)價(jià)一個(gè)用高級(jí)程序語言編寫的程序在計(jì)算機(jī)上運(yùn)行時(shí)所消耗的時(shí)間取決于下列因素：①依據(jù)的算法選用何種策略；②問題的規(guī)模.例如求100以內(nèi)還是1000以內(nèi)的

2、素?cái)?shù)；③書寫程序的語言.對(duì)于同一個(gè)算法,實(shí)現(xiàn)語言的級(jí)別越高,執(zhí)行效率就越低；④編譯程序所產(chǎn)生的機(jī)器代碼的質(zhì)量；⑤機(jī)器執(zhí)行指令的速度。算法評(píng)價(jià)一個(gè)算法是由控制結(jié)構(gòu)（順序、分支和循環(huán)三種）和原操作（指固有數(shù)據(jù)類型的操作）構(gòu)成的，則算法時(shí)間取決于兩者的綜合效果。為了便于比較同一問題的不同算法，通過的做法是，從算法中選取一種對(duì)于所研究的問題（或算法類型）來說是基本運(yùn)算的原操作，以該基本操作重復(fù)執(zhí)行的次數(shù)作為算法的時(shí)間度量。算法評(píng)價(jià)一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)f（n），算法的時(shí)間量度記作

3、T（n）=O（f（n））它表示問題規(guī)模n的增大算法執(zhí)行時(shí)間的增長率和f（n）的增長率相同，稱作算法的漸進(jìn)時(shí)間復(fù)雜度，簡稱時(shí)間復(fù)雜度。算法評(píng)價(jià)例如：在下列三個(gè)程序段中，①x:=x+1②fori:=1tondox:=x+1;③forj:=1tondofork:=1tondox:=x+1含基本操作“x增1”的語句x:=x+1的頻度分別為1，n和n2，則這三個(gè)程序段的時(shí)間復(fù)雜度分別為O（1），O（n），O（n2），分別稱為常量階、線性階和平方階。算法評(píng)價(jià)算法還可能呈現(xiàn)的時(shí)間復(fù)雜度有：對(duì)數(shù)階O（logn），指數(shù)階O（2n

4、）等。在n很大時(shí),不同數(shù)量級(jí)時(shí)間復(fù)雜度顯然有O（1）

5、度表達(dá)式(n-1)(n-2)/2中增長最快的一項(xiàng)。算法評(píng)價(jià)類似于算法的時(shí)間復(fù)雜度，以空間復(fù)雜度作為算法所需存儲(chǔ)空間的量度，記作S(n)=O(f(n))其中n為問題的規(guī)模(或大小)。一個(gè)上機(jī)執(zhí)行的程序除了需要存儲(chǔ)空間來寄存本身所用指令、常數(shù)、變量和輸入數(shù)據(jù)外，也需要一些對(duì)數(shù)據(jù)進(jìn)行操作的工作單元和存儲(chǔ)一些為實(shí)現(xiàn)計(jì)算所需信息的輔助空間。算法評(píng)價(jià)評(píng)價(jià)一個(gè)數(shù)學(xué)模型有以下幾個(gè)原則：1.時(shí)間復(fù)雜度一個(gè)好的算法一般效率比較高。在競賽中，試題常常會(huì)做一些算法運(yùn)行時(shí)間上的限制。這就要求我們所建立的數(shù)學(xué)模型對(duì)應(yīng)算法的效率一定要符合要

6、求。這也是最重要的一個(gè)原則。算法評(píng)價(jià)2.空間復(fù)雜度出于計(jì)算機(jī)自身的限制，程序在運(yùn)行時(shí)一般只被提供有限的內(nèi)存空間。這也就要求我們建立模型時(shí)顧及到這一點(diǎn)。但對(duì)于模型對(duì)應(yīng)的算法來說，并不是要求空間越低越好，只要不超過內(nèi)存限制就可以了。算法評(píng)價(jià)3.編程復(fù)雜度相對(duì)而言，“編程復(fù)雜度”的要求要略低一些。但是在競賽中，如果建立的算法實(shí)現(xiàn)起來十分繁瑣，自然不利于比賽。所以，在建立模型時(shí)（特別是在競賽中）這點(diǎn)也要納入考慮之中。影響算法效率的因素問題的算法模型的建立問題的數(shù)據(jù)結(jié)構(gòu)選擇算法評(píng)價(jià)一道題目可能對(duì)應(yīng)幾種不同思想的模型，就要

7、根據(jù)評(píng)價(jià)模型的標(biāo)準(zhǔn)來衡量一下，確定一個(gè)模型作為分析方向。這時(shí)的評(píng)價(jià)標(biāo)準(zhǔn)除了上述的時(shí)間、空間、編程三個(gè)標(biāo)準(zhǔn)外，還要加上一個(gè)思維的復(fù)雜度。算法評(píng)價(jià)所謂思維的復(fù)雜度，是指思考所耗費(fèi)的時(shí)間和精力。如果我們確定了一個(gè)模型作為分析的方向（沒有考慮思維復(fù)雜度），從問題原型到該數(shù)學(xué)模型的建模過程卻十分復(fù)雜，導(dǎo)致思維耗費(fèi)時(shí)間長，精力多，那自然是不合算的?？偟膩碚f，對(duì)于多種數(shù)學(xué)模型的選擇，我們遵循“邊分析，邊選擇”的原則。不同數(shù)據(jù)結(jié)構(gòu)對(duì)算法效率的影響乘船問題：有N個(gè)人需要乘船，而每船最多只能載兩人，且必須同名或同姓。求最少需要多少

8、條船。問題分析看到這道題，很多人都會(huì)想到圖的數(shù)據(jù)結(jié)構(gòu)：將N個(gè)人看作無向圖的N個(gè)點(diǎn)，凡同名或同姓的人之間都連上邊。要滿足用船最少的條件，就是需要盡量多的兩人共乘一條船，表現(xiàn)在圖中就是要用最少的邊完成對(duì)所有頂點(diǎn)的覆蓋。這就正好對(duì)應(yīng)了圖論的典型問題：求最小邊的覆蓋。所用的算法為“求任意圖最大匹配”的算法。分析使用“求任意圖最大匹配”的算法比較復(fù)雜(要用到擴(kuò)展交錯(cuò)樹，對(duì)花的收縮等等)，效率也不