2算法第二章導(dǎo)引詳解

其次章導(dǎo)引與基本數(shù)據(jù)結(jié)構(gòu)書目2.1算法2.2分析算法2.3用SPARKS語言寫算法2.4基本數(shù)據(jù)結(jié)構(gòu)(略)2.1算法什么是算法算法的重要特性計算過程與算法的區(qū)分問題的求解過程算法學(xué)習(xí)的基本內(nèi)容什么是算法算法是解決一確定類問題的隨意一種特殊的方法。數(shù)值計算方法非數(shù)值計算方法算法的非形式描述：算法就是一組有窮的規(guī)則，它規(guī)定了解決某一特定類型問題的一系列運(yùn)算。求解數(shù)值問題，插值計算、數(shù)值積分等。求解非數(shù)值問題，主要進(jìn)行推斷比較。算法(Algorithm)的五個重要特性確定性：每一種運(yùn)算必須要有精確定義，無二義性。例如：(1)5/0；(2)6或7與x相加。能行性：運(yùn)算都是基本運(yùn)算，原理上能由人用紙和筆在有限時間完成。輸入：有0個或多個輸入。輸出：一個或多個輸出。有窮性：在執(zhí)行了有窮步運(yùn)算后終止。僅僅有窮還不夠，還要在現(xiàn)代計算機(jī)上有效才行。計算過程與算法的區(qū)分計算過程可以不滿足算法的性質(zhì)(5)有窮性。例如操作系統(tǒng)，當(dāng)沒有任務(wù)時，操作系統(tǒng)并不終止，而是處于等待狀態(tài)，直到有新的任務(wù)啟動，因而不是一個算法。程序=算法+數(shù)據(jù)結(jié)構(gòu)(ByNiklausWirth)問題的求解過程證明正確性分析算法理解問題選擇數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計策略設(shè)計算法設(shè)計程序算法學(xué)習(xí)的基本內(nèi)容如何設(shè)計算法如何表示算法如何確認(rèn)算法如何分析算法如何測試程序如何設(shè)計算法面對具體問題，運(yùn)用一些基本設(shè)計策略被實(shí)踐證明是有用的一些基本設(shè)計策略計算機(jī)科學(xué)、運(yùn)籌學(xué)、電器工程等領(lǐng)域設(shè)計出很多精致有效的好算法駕馭這些策略，設(shè)計出更多的好算法如何表示算法設(shè)計的算法要用恰當(dāng)?shù)姆绞降乇硎境鰜斫邮芙Y(jié)構(gòu)程序設(shè)計的方式SPARKS程序設(shè)計語言——簡潔明白如何確認(rèn)算法算法確認(rèn)(algorithmvalidation)——證明該算法對全部可能的合法輸入，都能給出正確答案算法確認(rèn)的目的——確保該算法能正確無誤地工作窮舉法推理——數(shù)學(xué)歸納法、反證法構(gòu)造性證明測試如何分析算法分析執(zhí)行一個算法時，占用CPU時間完成運(yùn)算；占用存儲器的存儲空間，存放程序和數(shù)據(jù)。既對一個算法須要多少計算時間和存儲空間，做定量分析。如何測試程序

調(diào)試——調(diào)試只能指出有錯誤，而不能指出它們不存在錯誤。源于程序正確性的證明還沒有取得突破性進(jìn)展。時空分布圖用各種給定數(shù)據(jù)執(zhí)行調(diào)試后的程序測定計算時間和空間印證之前的分析是否正確指出實(shí)現(xiàn)最優(yōu)化的有效邏輯位置2.2分析算法算法分析目的算法分析的準(zhǔn)備工作計算時間的漸進(jìn)表示一些證明方法作時空性能分布圖算法分析的目的算法分析(analysisofalgorithms)是對一個算法須要多少計算時間和存儲空間作定量的分析?！_定算法在什么樣的環(huán)境下能夠有效地運(yùn)行。分析在最好、最壞和平均狀況下的執(zhí)行狀況。——對同一問題不同算法的有效性作出比較。時間困難性的形式化定義算法的時間困難性T(n)；算法的空間困難性S(n)；其中n是問題的規(guī)模。最壞狀況下：Tmax(n)=max{T(I)|size(I)=n}最好狀況下：Tmin(n)=min{T(I)|size(I)=n}平均狀況下：Tavg(n)=其中I是問題的規(guī)模為n的實(shí)例，p(I)是實(shí)例I出現(xiàn)的概率。算法運(yùn)行假定的計算機(jī)類型要求獨(dú)立于具體的軟硬件環(huán)境單純分析算法。假定運(yùn)用一臺通用計算機(jī)依次處理每條指令；存儲容量足夠大；存取時間恒定。算法分析過程確定算法所涉及的運(yùn)算分析算法語句的執(zhí)行次數(shù)分析算法的執(zhí)行時間的漸進(jìn)表示確定出能反映算法在各種狀況下工作的數(shù)據(jù)集作時空性能分布圖事前分析準(zhǔn)備工作事后測試全面分析的兩個階段準(zhǔn)備工作(一)首先確定運(yùn)用哪些運(yùn)算以及執(zhí)行這些運(yùn)算所用的時間?；具\(yùn)算由一些更基本的隨意長序列的運(yùn)算所組成的困難運(yùn)算基本運(yùn)算時間囿界于常數(shù)的運(yùn)算加、減、乘、除整數(shù)算術(shù)運(yùn)算浮點(diǎn)算術(shù)、字符比較、對變量賦值、過程調(diào)用等每種運(yùn)算所用時間雖然不同，但都只花費(fèi)一個固定量的時間困難運(yùn)算由一些更基本的隨意長序列的運(yùn)算組成如：兩個字符串的比較運(yùn)算一系列字符比較指令一個字符的比較時間——囿界于常數(shù)字符串比較的時間總量則取決于字符串的長度準(zhǔn)備工作(二)其次是要確定出能反映算法在各種狀況下工作的數(shù)據(jù)集。編造出能產(chǎn)生最好、最壞和有代表性狀況的數(shù)據(jù)配置通過運(yùn)用這些數(shù)據(jù)來運(yùn)行算法，以更了解算法的性能。算法分析最重要和最富于創(chuàng)建性的工作。全面分析算法的兩個階段事前分析(apriorianalysis)確定每條語句的執(zhí)行次數(shù)。求出該算法的一個時間限界函數(shù)(一些關(guān)于參數(shù)的函數(shù))。事后測試(aposteriortesting)作時空性能分布圖。算法的執(zhí)行時間同一條語句在一個算法中的執(zhí)行次數(shù)(frequencycount)稱為頻率計數(shù)語句的時間總量=頻率計數(shù)×執(zhí)行一次該語句所須要的時間算法的執(zhí)行時間就是構(gòu)成算法的全部語句的執(zhí)行時間總量之和由算法就可干脆確定，與所用的機(jī)器無關(guān)，且獨(dú)立于程序設(shè)計語言。依靠機(jī)器、程序設(shè)計語言、編譯程序例：計算語句xz+y在下面三個程序段中的頻率計數(shù)beginxz+yendFC:1beginfori1tondo

xz+yendFC:nbeginfori1tondoforj1tondo

xz+yendFC:n2語句的數(shù)量級是指執(zhí)行它的頻率算法的數(shù)量級是指算法的全部語句的執(zhí)行頻率之和確定一個算法的數(shù)量級特殊重要，因?yàn)樗诒举|(zhì)上反映了算法所需的計算時間。算法的數(shù)量級計算時間的基本特性描述算法數(shù)量級的多項(xiàng)表達(dá)式最高次項(xiàng)最高次項(xiàng)的系數(shù)最高次項(xiàng)的次數(shù)×××√精確分析出算法數(shù)量級的多項(xiàng)式表達(dá)式是很困難的，因此我們對事前分析的計算時間進(jìn)行漸進(jìn)表示。計算時間的漸進(jìn)表示定義2.1：f(n)=O(g(n))定義2.2：f(n)=Ω(g(n))定義2.3：f(n)=Θ(g(n))定理2.1變量和函數(shù)的含義n表示問題規(guī)模，輸入或輸出量；兩者之和；其中之一的某種測度。f(n)表示算法的計算時間。g(n)是在事前分析中確定的某個形式簡潔的函數(shù)。f(n)與機(jī)器和語言有關(guān)，而g(n)是獨(dú)立于機(jī)器和語言的。定義2.1假如存在兩個正常數(shù)c和n0，對于全部的n≥n0，有|f(n)|≤c|g(n)|，則記作：f(n)=O(g(n))。當(dāng)n充分大時，f(n)有上界，一個常數(shù)倍的g(n)是f(n)的一個上界，f(n)的數(shù)量級就是g(n)。f(n)的階不高于g(n)的階。在確定f(n)的數(shù)量級時，總是試圖求出最小的g(n)。有關(guān)證明中，找出c和n0是關(guān)鍵。推斷f(n)＝O(g(n))？f(n)＝3n,

g(n)=nf(n)＝n+1024,

g(n)=1025nf(n)＝2n2+11n-10,

g(n)=3n2f(n)＝n2,

g(n)=n3f(n)＝n3,

g(n)=n2O性質(zhì)對于非負(fù)的f(n)和g(n)，依據(jù)定義2.1，有如下性質(zhì)：1.O(f(n))+O(g(n))=O(max(f(n),g(n));2.O(f(n))+O(g(n))=O(f(n)+g(n))；3.O(f(n))O(g(n))=O(f(n)g(n))；4.假如g(n)=O(f(n))，則O(f(n))+O(g(n))=O(f(n))；5.O(cf(n))=O(f(n))，其中c是一個正的常數(shù)；6.f(n)=O(f(n))。定理2.1若A(n)=amnm+…+a1n+a0是一個m次多項(xiàng)式，則A(n)=O(nm)。證明：取n0=1，當(dāng)n≥n0時由A(n)的定義和不等式關(guān)系|A+B|≤|A|+|B|有

|A(n)|=|amnm+…+a1n+a0|≤|am|nm+…+|a1|

n+|a0| =(|am|+|am-1|/n…+|a0|/nm)

nm

≤(|am|+|am-1|…+|a0|)

nm取c=|am|+|am-1|…+|a0|，有|A(n)|≤cnm即：A(n)=O(nm)，定理得證。定理2.1表明，變量n的最高階數(shù)為m的任一多項(xiàng)式，與nm同階。因此一個計算時間為m階多項(xiàng)式的算法，其時間都可以用O(nm)來表示。

若一個算法有數(shù)量級為c1nm1，c2nm2，…cknmk的

k個語句，則算法的數(shù)量級及計算時間就是

c1nm1+c2nm2+…+cknmk=O(nm)

其中m=max{mi|1≤i≤k}定理2.1：若A(n)=amnm+…+a1n+a0是一個m次多項(xiàng)式，則A(n)=O(nm)。數(shù)量級對算法有效性的影響P25-26從計算時間上算法可以分為兩類：

多項(xiàng)式時間算法(polynomialtimealgorithm):

用多項(xiàng)式來對其計算時間限界的算法

O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)

指數(shù)時間算法(exponentialtimealgorithm):

計算時間用指數(shù)函數(shù)限界的算法

O(2n)<O(n!)<O(nn)不同時間困難性函數(shù)的對比定義2.2當(dāng)n充分大時，f(n)有下界，一個常數(shù)倍的g(n)是f(n)的一個下界。f(n)的階不低于g(n)的階。在確定f(n)的下界時，總是試圖求出最大的g(n)。有關(guān)證明中，找出c和n0是關(guān)鍵。假如存在兩個正常數(shù)c和n0，對于全部的n≥n0，有|f(n)|≥c|g(n)|，則記作：f(n)=Ω(g(n))。性質(zhì)對于非負(fù)的f(n)和g(n)，依據(jù)定義2.2，有如下性質(zhì)：1.(f(n))+(g(n))=(min(f(n),g(n));2.(f(n))+(g(n))=(f(n)+g(n))；3.(f(n))(g(n))=(f(n)g(n))；4.假如g(n)=(f(n))，則(f(n))+(g(n))=(f(n))；5.(cf(n))=(f(n))，其中c是一個正的常數(shù)；6.f(n)=(f(n))。定義2.3一個算法的f(n)=Θ(g(n))意味著該算法在最好和最壞狀況下的計算時間就一個常數(shù)因子范圍內(nèi)而言是相同的。假如存在正常數(shù)c1,c2和n0，對于全部的n≥n0，有c1|g(n)|≤|f(n)|≤c2|g(n)|，則記作：f(n)=Θ(g(n))。漸近表示函數(shù)的若干性質(zhì)傳遞性f(n)=(g(n))，g(n)=(h(n))

f(n)=(h(n))；f(n)=O(g(n))，g(n)=O

(h(n))

f(n)=O

(h(n))；f(n)=(g(n))，g(n)=(h(n))

f(n)=(h(n))；反身性f(n)=(f(n))；f(n)=O(f(n))；f(n)=(f(n))。常用的整數(shù)求和公式通式：一些數(shù)學(xué)證明方法干脆證明：PQ間接證明：反證法舉反例數(shù)學(xué)歸納法：初始?xì)w納：i=1結(jié)論成立；歸納假設(shè)：若i=n-1時成立；歸納證明：證明i=n時成立。作時空性能分布圖事后測試是在對算法進(jìn)行設(shè)計、確認(rèn)、事前分析和調(diào)試之后要做的工作，與所用計算機(jī)親密相關(guān)。以時間分布圖為例：算法時間的精確測量 分布圖的做法－>數(shù)據(jù)集與時間困難度有關(guān)時鐘不精確造成的噪聲增大規(guī)模重復(fù)執(zhí)行2.3用SPARKS語言寫算法P28-33作業(yè)1證明:n2=O(n3);證明:2n2+11n-10=O(n2);證明：O的以下兩特性質(zhì)O(f(n))O(g(n))=O(f(n)g(n));O(cf(n))=O(f(n))，其中c是一個正的常數(shù)；證明：n3O(n2)作業(yè)15.如果g(n)=

(f(n))，則

(f(n))+

(g(n))