第1章算法概述1

計(jì)算機(jī)算法設(shè)計(jì)與分析

DesignandAnalysisofComputerAlgorithms

第一章算法概述王紅霞理學(xué)院2/4/20231理解算法的概念。理解什么是程序，程序與算法的區(qū)別和內(nèi)在聯(lián)系。掌握算法的計(jì)算復(fù)雜性概念。掌握算法漸近復(fù)雜性的數(shù)學(xué)表述。掌握用C++語(yǔ)言描述算法的方法學(xué)習(xí)要點(diǎn):2提綱一、算法與程序二、算法復(fù)雜性分析三、用C++語(yǔ)言描述算法的方法3提綱一、算法與程序二、算法復(fù)雜性分析三、用C++語(yǔ)言描述算法的方法4

在中央電視臺(tái)幸運(yùn)52節(jié)目中,有一個(gè)猜商品價(jià)格的環(huán)節(jié),竟猜者如在規(guī)定的時(shí)間內(nèi)大體猜出某種商品的價(jià)格,就可獲得該件商品.現(xiàn)有一商品,價(jià)格在0-8000元之間,采取怎樣的策略才能在短的時(shí)間內(nèi)說(shuō)出正確(大體上)的答案呢?第一步:報(bào)“4000”；第二步:若主持人說(shuō)高了(說(shuō)明答案在0~4000之間),就報(bào)“2000”,否則(答數(shù)在4000~8000之間)報(bào)“6000”；第三步:重復(fù)第二步的報(bào)數(shù)方法取中間數(shù),直至得到正確結(jié)果.5兩個(gè)大人和兩名兒童一起渡河，渡口只有一條小船，一次只能渡過(guò)一個(gè)大人或兩名兒童，他們四人都會(huì)劃船，但都不會(huì)游泳。請(qǐng)你幫他們?cè)O(shè)計(jì)一個(gè)渡河方案。什么是算法呢？第一步：兩個(gè)小孩同船渡過(guò)河去；第二步：一個(gè)小孩劃船回來(lái)；第三步：一個(gè)大人獨(dú)自劃船渡過(guò)河去；第四步：對(duì)岸的小孩劃船回來(lái)；第五步：兩個(gè)小孩再同船渡過(guò)河去；第六步：一個(gè)小孩劃船回來(lái)；第七步：余下的一個(gè)大人獨(dú)自劃船渡過(guò)河去；第八步：對(duì)岸的小孩劃船回來(lái)；第九步：兩個(gè)小孩再同船渡過(guò)河去。6什么是算法呢？簡(jiǎn)單地說(shuō)，算法就是解決問(wèn)題的方法或步驟。7你對(duì)以下的“算法”如何理解？要把大象裝冰箱，分幾步？答：分三步：第一步：打開(kāi)冰箱門(mén)第二步：把大象裝冰箱第三步：關(guān)上冰箱門(mén)問(wèn)：?jiǎn)栴}38一位商人有9枚金幣，其中有一枚略輕的假幣，你能用天平（無(wú)砝碼）將假幣找出來(lái)嗎？寫(xiě)出解決這一問(wèn)題的算法。第一步：把9枚金幣平均分成三組，每組三枚。先將其中的兩組放在天平的兩邊，如果天平不平衡，那么假金幣就在輕的那一組；如果天平左右平衡，則假金幣就在未稱(chēng)量的那一組里。取出含假幣的那一組，從中任取兩枚金幣放在天平兩邊進(jìn)行稱(chēng)量，如果天平不平衡，則假金幣在輕的那一邊；若平衡，則未稱(chēng)的那一枚就是假幣。第二步：第三步：?jiǎn)栴}491.1算法的概念算法是指解決問(wèn)題的方法和過(guò)程。算法是對(duì)特定問(wèn)題求解步驟的一種描述，包含操作的有限規(guī)則和操作的有限序列。通俗一點(diǎn)講，算法就是一個(gè)解決問(wèn)題的公式（數(shù)學(xué)手冊(cè)上的公式都是經(jīng)典算法）、規(guī)則、思路、方法和步驟。算法可以用自然語(yǔ)言描述，也可以用流程圖描述，但最終要用計(jì)算機(jī)語(yǔ)言編程，上機(jī)實(shí)現(xiàn)。

10從更廣義的角度來(lái)看,并不是只有“計(jì)算”的問(wèn)題才有算法,日常生活中處處都有.如樂(lè)譜是樂(lè)隊(duì)演奏的算法,菜譜是做菜肴的算法,珠算口訣是使用算盤(pán)的算法.

人們的生產(chǎn)活動(dòng)和日常生活離不開(kāi)算法，都在自覺(jué)不自覺(jué)地使用算法，例如人們到商店購(gòu)買(mǎi)物品，會(huì)首先確定購(gòu)買(mǎi)哪些物品，準(zhǔn)備好所需的錢(qián)，然后確定到哪些商場(chǎng)選購(gòu)、怎樣去商場(chǎng)、行走的路線，若物品的質(zhì)量好如何處理，對(duì)物品不滿意又怎樣處理，購(gòu)買(mǎi)物品后做什么等。以上購(gòu)物的算法是用自然語(yǔ)言描述的，也可以用其他描述方法描述該算法。

11算法的特性算法是若干指令的有窮序列，滿足性質(zhì)：輸入：有1個(gè)或多個(gè)滿足給定約束條件的量作為算法的輸入。輸出：算法產(chǎn)生至少一個(gè)量作為輸出。確定性：組成算法的每條指令是清晰，無(wú)歧義的。有限性：算法中每條指令的執(zhí)行次數(shù)是有限的，執(zhí)行每條指令的時(shí)間也是有限的。算法要求其執(zhí)行時(shí)間是有限的(終止性)。程序的執(zhí)行時(shí)間可能是無(wú)限的。(例操作系統(tǒng)，只要整個(gè)系統(tǒng)不遭破壞，它將永遠(yuǎn)不會(huì)停止，即使沒(méi)有作業(yè)需要處理，它仍處于動(dòng)態(tài)等待中。因此，操作系統(tǒng)不是一個(gè)算法。)12以累加10個(gè)1的算法為例不正確的算法(無(wú)結(jié)束)第一步開(kāi)始第二步N=0第三步N=N+1第四步轉(zhuǎn)第三步第五步結(jié)束不正確的算法(指令不清晰

)第一步開(kāi)始第二步N=0第三步N=N+1第四步根據(jù)N值轉(zhuǎn)第三步或第五步第五步結(jié)束正確的算法第一步開(kāi)始第二步N=0第三步N=N+1第四步N>9轉(zhuǎn)第五步否則轉(zhuǎn)第三步第五步結(jié)束13程序程序是某個(gè)算法或過(guò)程的在計(jì)算機(jī)上的一個(gè)具體的實(shí)現(xiàn)。程序是依賴(lài)于程序設(shè)計(jì)語(yǔ)言的，甚至依賴(lài)于計(jì)算機(jī)結(jié)構(gòu)的。算法是脫離具體的計(jì)算機(jī)結(jié)構(gòu)和程序設(shè)計(jì)語(yǔ)言的。14算法與程序的區(qū)別與聯(lián)系(1).一個(gè)程序不一定滿足有窮性。例操作系統(tǒng)，只要整個(gè)系統(tǒng)不遭破壞，它將永遠(yuǎn)不會(huì)停止，即使沒(méi)有作業(yè)需要處理，它仍處于動(dòng)態(tài)等待中。因此，操作系統(tǒng)不是一個(gè)算法。(2).程序中的指令必須是機(jī)器可執(zhí)行的，而算法中的指令則無(wú)此限制。(3).算法代表了對(duì)問(wèn)題的解，而程序則是算法在計(jì)算機(jī)上的特定的實(shí)現(xiàn)。一個(gè)算法若用程序設(shè)計(jì)語(yǔ)言來(lái)描述，則它就是一個(gè)程序.15算法≠程序算法描述：自然語(yǔ)言，流程圖，程序設(shè)計(jì)語(yǔ)言，偽代碼用各種算法描述方法所描述的同一算法，該算法的功用是一樣的，允許在算法的描述和實(shí)現(xiàn)方法上有所不同。本書(shū)中采用類(lèi)C++偽代碼語(yǔ)言描述算法16算法的表示自然語(yǔ)言流程圖偽代碼計(jì)算機(jī)語(yǔ)言17用自然語(yǔ)言表示算法自然語(yǔ)言就是人們?nèi)粘Ｊ褂玫恼Z(yǔ)言，可以是英語(yǔ)、漢語(yǔ)或其它語(yǔ)言。用自然語(yǔ)言表示算法通俗易懂，但文字冗長(zhǎng)，含義不太嚴(yán)格，容易出現(xiàn)“歧義性”。此外，用自然語(yǔ)言表示包含分支和循環(huán)的算法也不方便。18用流程圖表示算法流程圖是用一些事先規(guī)定了具有某種含義的圖框和流程線來(lái)表示算法中的步驟和各種操作。用流程圖表示算法直觀形象，邏輯清晰，但是占用篇幅較多，尤其當(dāng)算法比較復(fù)雜時(shí)，畫(huà)流程圖既費(fèi)時(shí)又不方便，而且當(dāng)算法不斷改動(dòng)時(shí)，流程圖的修改也非常麻煩，因此流程圖宜用于表示一個(gè)完成的最終算法。流程圖有很多種類(lèi)型：傳統(tǒng)流程圖，N－S流程圖19傳統(tǒng)流程圖起止框處理框輸入輸出框判斷框連接點(diǎn)流程線NoYesn≤5開(kāi)始結(jié)束p=1n=1p=p*nn=n+1傳統(tǒng)流程圖中由于對(duì)流程線的使用沒(méi)有嚴(yán)格限制，所有很容易造成流程圖的混亂和無(wú)規(guī)律。這是用傳統(tǒng)流程圖表示的求1×2×3×4×5的算法：20三種基本程序結(jié)構(gòu)為了提高算法的質(zhì)量，使算法設(shè)計(jì)和閱讀方便，必須限制流程線的濫用，即不允許無(wú)規(guī)律的使流程轉(zhuǎn)向，只能順序的進(jìn)行下去。但是。算法中難免會(huì)包含一些分支和循環(huán)而不可能全部由一個(gè)一個(gè)框順序組成。為了解決這個(gè)問(wèn)題，人們規(guī)定出幾種基本結(jié)構(gòu)，然后由這些基本結(jié)構(gòu)按一定規(guī)律順序排列,組成一個(gè)算法結(jié)構(gòu)，整個(gè)算法的描述是由上而下的將各個(gè)基本結(jié)構(gòu)順序排列起來(lái)。A?YesNoabABabAB?YesNoab順序結(jié)構(gòu)選擇結(jié)構(gòu)循環(huán)結(jié)構(gòu)21N－S流程圖既然用基本結(jié)構(gòu)的順序組合就可以表示任何復(fù)雜的算法結(jié)構(gòu)，那么，基本結(jié)構(gòu)之間的流程線就是多余的了。在Ｎ－Ｓ流程圖中，完全去掉了帶箭頭的流程線。全部算法寫(xiě)在一個(gè)矩形框內(nèi)，在該框內(nèi)還可以包含其它從屬于它的框，或者說(shuō)，由一些基本的框組成一個(gè)大的框。AB順序結(jié)構(gòu)選擇結(jié)構(gòu)循環(huán)結(jié)構(gòu)Ｎ－Ｓ流程圖中使用以下的流程圖符號(hào)：條件?AB成立不成立當(dāng)條件成立做A做到條件不成立A當(dāng)條件成立做while,做到條件成立until(條件不成立做,做到條件成立停)

在C語(yǔ)言為了簡(jiǎn)練,沒(méi)有until,只有while,條件成立做,條件不成立不做,

所以改”到”型循環(huán)為做到條件不成立,與”當(dāng)”型循環(huán)的條件一樣22用N-S流程圖表示的求1×2×3×4×5的算法：N<=5P=P*NN=N+1N=1P=1輸出P

N<=5P=P*NN=N+1N=1P=1輸出P條件成立做做到條件不成立23用偽代碼表示算法為了設(shè)計(jì)算法時(shí)的方便，常用一種稱(chēng)為“偽代碼”的方法?！皞未a”是用介于自然語(yǔ)言和計(jì)算機(jī)語(yǔ)言之間的文字和符號(hào)來(lái)描述算法。它如同一篇文章。自上而下地寫(xiě)下來(lái)。每一行（或幾行）表示一個(gè)基本操作。它不用圖形符號(hào)。因此書(shū)寫(xiě)方便。格式緊湊，也比較好懂，便于向計(jì)算機(jī)語(yǔ)言算法（即程序）過(guò)渡。24用計(jì)算機(jī)語(yǔ)言表示算法在用“流程圖”或“偽代碼”描述出一個(gè)算法后，還要將它轉(zhuǎn)換成計(jì)算機(jī)語(yǔ)言程序，這樣才能執(zhí)行程序并得到結(jié)果。從而最終解決實(shí)際問(wèn)題。用計(jì)算機(jī)語(yǔ)言表示算法必須嚴(yán)格遵守所用語(yǔ)言的語(yǔ)法規(guī)則。下面是用Ｃ語(yǔ)言編寫(xiě)的求1×2×3×4×5的程序：#include<stdio.h>intmain(){intn=1,prod=1;while(n<=5){prod=prod*n;n++;}printf(“prod=%d\n”,prod);return(0);}do{prod=prod*n;n++;}while(n<=5);25對(duì)算法的學(xué)習(xí)包括五個(gè)方面的內(nèi)容：①設(shè)計(jì)算法。②表示算法。③確認(rèn)算法。④分析算法。⑤驗(yàn)證算法。26①設(shè)計(jì)算法。算法設(shè)計(jì)工作是不可能完全自動(dòng)化的，應(yīng)學(xué)習(xí)了解已經(jīng)被實(shí)踐證明是有用的一些基本的算法設(shè)計(jì)方法，這些基本的設(shè)計(jì)方法不僅適用于計(jì)算機(jī)科學(xué)，而且適用于電氣工程、運(yùn)籌學(xué)等領(lǐng)域；②表示算法。描述算法的方法有多種形式，例如自然語(yǔ)言和算法語(yǔ)言，各自有適用的環(huán)境和特點(diǎn)；27③確認(rèn)算法。算法確認(rèn)的目的是使人們確信這一算法能夠正確無(wú)誤地工作，即該算法具有可計(jì)算性。正確的算法用計(jì)算機(jī)算法語(yǔ)言描述，構(gòu)成計(jì)算機(jī)程序，計(jì)算機(jī)程序在計(jì)算機(jī)上運(yùn)行，得到算法運(yùn)算的結(jié)果；④分析算法。算法分析是對(duì)一個(gè)算法需要多少計(jì)算時(shí)間和存儲(chǔ)空間作定量的分析。分析算法可以預(yù)測(cè)這一算法適合在什么樣的環(huán)境中有效地運(yùn)行，對(duì)解決同一問(wèn)題的不同算法的有效性作出比較；⑤驗(yàn)證算法。用計(jì)算機(jī)語(yǔ)言描述的算法是否可計(jì)算、有效合理，須對(duì)程序進(jìn)行測(cè)試，測(cè)試程序的工作由調(diào)試和作時(shí)空分布圖組成。

281.2問(wèn)題表示設(shè)Input和Output是兩個(gè)集合。一個(gè)問(wèn)題是一個(gè)關(guān)系RInputOutput，Input稱(chēng)為問(wèn)題R的輸入集合，Input的每個(gè)元素稱(chēng)為R的一個(gè)輸入，Output稱(chēng)為問(wèn)題R的輸出或結(jié)果集合，Output的每個(gè)元素稱(chēng)為R的一個(gè)結(jié)果。一個(gè)算法面向一類(lèi)問(wèn)題，而不是僅求解問(wèn)題的一個(gè)或幾個(gè)實(shí)例。291.2問(wèn)題表示例如，排序（SORT）問(wèn)題定義如下：－Input=<a1,....,an>ai是實(shí)數(shù)－output=<b1,....,bn>bi是實(shí)數(shù),且b1...bn－R=(<a1,...,an>,<b1,...,bn>)<a1,...,an>Input，<b1,...,bn>output,a1,...,an=b1,...,bn}30a0,...,n-1=5,2,4,6,1,3a0,...,n-1=5,2,4,6,1,3a0,...,n-1=2,5,4,6,1,3a0,...,n-1=2,4,5,6,1,3a0,...,n-1=2,4,5,6,1,3a0,...,n-1=1,2,4,5,6,3a0,...,n-1=1,2,3,4,5,6算法的思想：撲克牌游戲1.3算法示例—插入排序算法31算法描述1.從第一個(gè)元素開(kāi)始，該元素可以認(rèn)為已經(jīng)被排序2.取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描3.如果該元素（已排序）大于新元素，將該元素移到下一位置4.重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置5.將新元素插入到該位置中6.重復(fù)步驟2321.3算法示例插入排序算法

template<classType>voidInsertionSort(Type*a,intn)//數(shù)組a中包含了n個(gè)待排序的數(shù).{Typekey;for(inti=1;i<n;i++){key=a[i];//Inserta[i]intothesortedsequencea[0..i-1].intj=i-1;while(j>=0&&a[j]>key){ a[j+1]=a[j]; j--; }a[j+1]=key;}}331.4算法的正確性分析正確的算法：對(duì)于每一個(gè)輸入都最終停止,而且產(chǎn)生正確的輸出。不正確算法：①不停止(在某個(gè)輸入上)②對(duì)所有輸入都停止，但對(duì)某輸入產(chǎn)生不正確結(jié)果近似算法①對(duì)所有輸入都停止②產(chǎn)生近似正確的解或產(chǎn)生不多的不正確解算法正確性證明證明算法對(duì)所有輸入都停止證明對(duì)每個(gè)輸入都產(chǎn)生正確結(jié)果調(diào)試程序程序正確性證明！程序調(diào)試只能證明程序有錯(cuò)，不能證明程序無(wú)錯(cuò)誤!341.4算法的正確性分析算法正確性證明的步驟：初始化算法在循環(huán)的第一步迭代開(kāi)始之前，應(yīng)該是正確的。保持如果在循環(huán)的某一次迭代開(kāi)始之前它是正確的，那么，在下一次迭代開(kāi)始之前，它也應(yīng)該保持正確。終止當(dāng)循環(huán)結(jié)束時(shí)，算法也應(yīng)該是正確的。分析前面插入排序算法的正確性35如果根據(jù)應(yīng)用領(lǐng)域進(jìn)行分類(lèi)的話，算法的種類(lèi)就更多了。每種應(yīng)用領(lǐng)域都會(huì)有大量的算法。一些典型的算法包括排序算法、搜索算法、圖論算法、機(jī)器學(xué)習(xí)、加密算法、數(shù)據(jù)壓縮算法、語(yǔ)法分析算法、數(shù)論與代數(shù)算法等。36算法設(shè)計(jì)與分析的基本方法1.遞推法

遞推法是利用問(wèn)題本身所具有的一種遞推關(guān)系求問(wèn)題解的一種方法。它把問(wèn)題分成若干步，找出相鄰幾步的關(guān)系，從而達(dá)到目的，此方法稱(chēng)為遞推法。

372.遞歸

遞歸指的是一個(gè)過(guò)程：函數(shù)不斷引用自身，直到引用的對(duì)象已知

3.窮舉搜索法

窮舉搜索法是對(duì)可能是解的眾多候選解按某種順序進(jìn)行逐一枚舉和檢驗(yàn)，并從眾找出那些符合要求的候選解作為問(wèn)題的解。

384.貪婪法

貪婪法是一種不追求最優(yōu)解，只希望得到較為滿意解的方法。貪婪法一般可以快速得到滿意的解，因?yàn)樗∪チ藶檎易顑?yōu)解要窮盡所有可能而必須耗費(fèi)的大量時(shí)間。貪婪法常以當(dāng)前情況為基礎(chǔ)作最優(yōu)選擇，而不考慮各種可能的整體情況，所以貪婪法不要回溯。

395.分治法

把一個(gè)復(fù)雜的問(wèn)題分成兩個(gè)或更多的相同或相似的子問(wèn)題，再把子問(wèn)題分成更小的子問(wèn)題……直到最后子問(wèn)題可以簡(jiǎn)單的直接求解，原問(wèn)題的解即子問(wèn)題的解的合并。

406.動(dòng)態(tài)規(guī)劃法

動(dòng)態(tài)規(guī)劃是一種在數(shù)學(xué)和計(jì)算機(jī)科學(xué)中使用的，用于求解包含重疊子問(wèn)題的最優(yōu)化問(wèn)題的方法。其基本思想是，將原問(wèn)題分解為相似的子問(wèn)題，在求解的過(guò)程中通過(guò)子問(wèn)題的解求出原問(wèn)題的解。動(dòng)態(tài)規(guī)劃的思想是多種算法的基礎(chǔ)，被廣泛應(yīng)用于計(jì)算機(jī)科學(xué)和工程領(lǐng)域。

417.迭代法

迭代是數(shù)值分析中通過(guò)從一個(gè)初始估計(jì)出發(fā)尋找一系列近似解來(lái)解決問(wèn)題（一般是解方程或者方程組）的過(guò)程，為實(shí)現(xiàn)這一過(guò)程所使用的方法統(tǒng)稱(chēng)為迭代法。42提綱一、算法與程序二、算法復(fù)雜性分析三、用C++語(yǔ)言描述算法的方法43

算法復(fù)雜性分析對(duì)于給定的問(wèn)題，起初只是考慮只要找到一個(gè)算法解決該問(wèn)題就行，而不管該算法花多長(zhǎng)時(shí)間或者占用多大的存儲(chǔ)空間。隨著計(jì)算機(jī)技術(shù)的發(fā)展，人們發(fā)現(xiàn)，求解同一個(gè)問(wèn)題的不同的算法，所需要的運(yùn)行時(shí)間是不同的。例如對(duì)排序問(wèn)題，除了插入排序算法，還有選擇排序、合并排序以及快速排序算法。我們自然會(huì)問(wèn)，哪個(gè)排序算法好呢？怎么樣評(píng)價(jià)一個(gè)算法的好壞呢？這就涉及到算法的時(shí)間和空間資源的分析，即算法效率(Efficiency)的分析。44算法復(fù)雜性分析算法效率的分析，指的是算法求解一個(gè)問(wèn)題所需要的時(shí)間和空間。分析一個(gè)算法，意味著預(yù)測(cè)該算法解一個(gè)問(wèn)題時(shí)，需要花費(fèi)多少時(shí)間和空間資源?？臻g資源一般指解決一個(gè)問(wèn)題，需要多大的內(nèi)存、硬盤(pán)空間等來(lái)存儲(chǔ)輸入輸出數(shù)據(jù)等。時(shí)間資源一般指的是解決一個(gè)問(wèn)題需要多長(zhǎng)的時(shí)間。一般地，對(duì)一個(gè)問(wèn)題，存在不同的求解算法，我們可以根據(jù)算法所需要的時(shí)空資源來(lái)確定出其中有效的算法。隨著計(jì)算機(jī)硬件技術(shù)的發(fā)展，現(xiàn)在計(jì)算機(jī)的內(nèi)存和硬盤(pán)空間基本上能滿足問(wèn)題的需要，即空間資源已經(jīng)不是問(wèn)題，因此，我們分析一個(gè)算法，主要考慮算法的計(jì)算時(shí)間，今后，我們也主要從時(shí)間資源方面對(duì)算法進(jìn)行分析，即分析算法有多快。45同一問(wèn)題可用不同算法解決，而一個(gè)算法的質(zhì)量?jī)?yōu)劣將影響到算法乃至程序的效率。算法分析的目的在于選擇合適算法和改進(jìn)算法。一個(gè)算法的評(píng)價(jià)主要從時(shí)間復(fù)雜度和空間復(fù)雜度來(lái)考慮。46二、算法復(fù)雜性分析算法復(fù)雜性=算法所需要的計(jì)算機(jī)資源所需資源量越多則復(fù)雜性越高，反之所需資源量越少則復(fù)雜性越低。其中最為重要的是：時(shí)間復(fù)雜性T(n)；空間復(fù)雜性S(n)。其中n是問(wèn)題的規(guī)模（輸入大?。Ｊ纠阂痪S數(shù)組問(wèn)題的輸入大?。綌?shù)組的長(zhǎng)度矩陣問(wèn)題的輸入大小=矩陣的維數(shù)圖論問(wèn)題的輸入大小=圖的邊數(shù)/結(jié)點(diǎn)數(shù)47決定算法復(fù)雜性的因素算法的復(fù)雜性取決于(1)求解問(wèn)題的規(guī)模；(2)具體的輸入數(shù)據(jù)；(3)算法本身的設(shè)計(jì)。若令N、I、和A分別表示問(wèn)題的規(guī)模、具體的輸入和算法本身，則C=F(N,I,A)或C=FA(N,I)=F(N,I)48時(shí)間復(fù)雜性的計(jì)算時(shí)間復(fù)雜性T(N,I)的計(jì)算為：

其中：ti為執(zhí)行抽象計(jì)算機(jī)的第i種指令一次所需要的時(shí)間，這里假定抽象計(jì)算機(jī)共有k種指令。ei(N,I)為經(jīng)過(guò)統(tǒng)計(jì)后得到的執(zhí)行抽象計(jì)算機(jī)的第i種指令的次數(shù)。kT(N,I)=tiei(N,I)

i=149二、算法復(fù)雜性分析算法分析的目的：設(shè)計(jì)算法——設(shè)計(jì)出復(fù)雜性盡可能低的算法選擇算法——在多種算法中選擇其中復(fù)雜性最低者502.1算法時(shí)間復(fù)雜性最壞情況下的時(shí)間復(fù)雜性Tmax(n)=max{T(I)|size(I)=n}最好情況下的時(shí)間復(fù)雜性Tmin(n)=min{T(I)|size(I)=n}平均情況下的時(shí)間復(fù)雜性Tavg(n)=

其中I是問(wèn)題的規(guī)模為n的實(shí)例，p(I)是實(shí)例I出現(xiàn)的概率。512.2時(shí)間復(fù)雜性計(jì)算為了能夠較客觀的反映出一個(gè)算法的效率，在度量一個(gè)算法的工作量時(shí)，不僅應(yīng)該與所使用的計(jì)算機(jī)、程序設(shè)計(jì)語(yǔ)言以及程序編制者無(wú)關(guān)，而且還應(yīng)該與算法實(shí)現(xiàn)過(guò)程中的許多細(xì)節(jié)無(wú)關(guān)。為此，可以用算法在執(zhí)行過(guò)程中所需基本運(yùn)算的執(zhí)行次數(shù)來(lái)度量算法的工作量。基本運(yùn)算反映了算法運(yùn)算的主要特征，因此，用基本運(yùn)算的次數(shù)來(lái)度量算法工作量是客觀的也是實(shí)際可行的，有利于比較同一問(wèn)題的幾種算法的優(yōu)劣。例如，在考慮兩個(gè)矩陣相乘時(shí)，可以將兩個(gè)實(shí)數(shù)之間的乘法運(yùn)算作為基本運(yùn)算.522.2時(shí)間復(fù)雜性計(jì)算在一般的計(jì)算機(jī)系統(tǒng)中，基本的運(yùn)算和操作有以下四類(lèi)：

①算術(shù)運(yùn)算：主要包括加、減、乘、除等運(yùn)算。

②邏輯運(yùn)算：主要包括“與”、“或”、“非”等運(yùn)算。

③關(guān)系運(yùn)算：主要包括“大于”、“小于”、“等于”、“不等于”等運(yùn)算。

④數(shù)據(jù)傳輸：主要包括賦值、輸入、輸出等操作。規(guī)定其中每條指令所需的時(shí)間都為常量。算法的執(zhí)行時(shí)間=原子操作的執(zhí)行次數(shù)×原子操作的執(zhí)行時(shí)間53template<classType>voidInsertionSort(Type*a,intn){Typekey;//costtimesfor(inti=1;i<n;i++){//c1n

key=a[i];//c2n-1

intj=i-1;//c3n-1

while(j>=0&&a[j]>key){//c4sumofti a[j+1]=a[j];//c5sumof(ti-1)

j--;//c6sumof(ti-1) }a[j+1]=key;//c7n-1

}}2.2時(shí)間復(fù)雜性計(jì)算54在最好情況下，ti=1,for1

i<n;在最壞情況下，ti＝

i+1,for1

i<n;2.2時(shí)間復(fù)雜性計(jì)算55算法的時(shí)間復(fù)雜度如果目標(biāo)是把n個(gè)元素的序列升序排列，那么采用插入排序存在最好情況和最壞情況。最好情況就是，序列已經(jīng)是升序排列了，在這種情況下，需要進(jìn)行的比較操作需(n-1)次即可。最壞情況就是，序列是降序排列，那么此時(shí)需要進(jìn)行的比較共有n(n-1)/2次。插入排序的賦值操作是比較操作的次數(shù)加上(n-1)次。平均來(lái)說(shuō)插入排序算法的時(shí)間復(fù)雜度為O(n2)。因而，插入排序不適合對(duì)于數(shù)據(jù)量比較大的排序應(yīng)用。但是，如果需要排序的數(shù)據(jù)量很小，例如，量級(jí)小于千，那么插入排序還是一個(gè)不錯(cuò)的選擇。56復(fù)雜性分析的簡(jiǎn)化令T(N)為表示算法A的復(fù)雜性函數(shù)，若存在?(N)，使得LimN(T(N)–?(N))/T(N)=0那么，就可以用?(N)來(lái)代替T(N)，從而簡(jiǎn)化復(fù)雜性的分析。例如：T(N)=3N2+4NlogN+7，?(N)=3N2，則

LimN(T(N)–?(N))/T(N)=LimN4NlogN+7/3N2+4NlogN+7=057用階來(lái)表示復(fù)雜性在漸進(jìn)復(fù)雜性分析中，只要關(guān)心?(N)的階就夠了，不必關(guān)心?(N)中的常數(shù)因子，這樣我們就只需要用?(N)的階來(lái)表示該算法的復(fù)雜性。例如，計(jì)算一個(gè)N維矩陣A的平方的時(shí)間復(fù)雜性可估算為2N*N2=2N3，即此計(jì)算的時(shí)間復(fù)雜性為3階。582.3時(shí)間復(fù)雜性的漸近性態(tài)時(shí)間復(fù)雜性的漸近性態(tài)：(T(n)-t(n))/T(n)0，asn;t(n)是T(n)的漸近性態(tài)，為算法的漸近復(fù)雜性。在數(shù)學(xué)上，t(n)是T(n)的漸近表達(dá)式，是T(n)略去低階項(xiàng)留下的主項(xiàng)。它比T(n)簡(jiǎn)單。59幾個(gè)記號(hào)設(shè)f(N)、g(N)都是定義在正整數(shù)集上的函數(shù)。上界記號(hào)O：如果存在正的常數(shù)C和自然數(shù)N0，使得當(dāng)N≧N0

時(shí)有f(N)≦Cg(N)，則f(N)有上界函數(shù)g(N)，記為f(N)=O(g(N))。下界記號(hào)Ω：如果存在正的常數(shù)C和自然數(shù)N0，使得當(dāng)N≧N0

時(shí)有f(N)≧Cg(N)，則f(N)有下界函數(shù)g(N)，記為f(N)=Ω(g(N))。同階記號(hào)Θ：f(N)=Θ(g(N))表示f(N)和g(N)同階。低階記號(hào)o：f(N)=o(g(N))表示f(N)比g(N)低階602.3時(shí)間復(fù)雜性的漸近性態(tài)漸近上界記號(hào)OO(g(n))={f(n)|存在正常數(shù)c和n0使得對(duì)所有nn0有：0f(n)

cg(n)}例如：3n-10=O(n);n2+2n+3=O(n2);3logn+loglogn=O(logn);常數(shù)=O(1)612.3時(shí)間復(fù)雜性的漸近性態(tài)大O的運(yùn)算性質(zhì)：O(f)+O(g)=O(max(f,g));O(f)+O(g)=O(f+g);O(f)O(g)=O(fg);如果g(n)=O(f(n)),則O(f)+O(g)=O(f);O(cf(n))=O(f(n)),其中c是一個(gè)正的常數(shù)；f=O(f);如果f(n)是次數(shù)為d的多項(xiàng)式，即f(n)=adnd+…+a1n+a0，則f(n)=O(nd)在大O符號(hào)中包含常數(shù)因子和低階項(xiàng)被認(rèn)為是不好的。應(yīng)該用大O的最簡(jiǎn)單形式描述算法的時(shí)間復(fù)雜性。應(yīng)該用大O符號(hào)盡可能接近地表征一個(gè)函數(shù)。622.3時(shí)間復(fù)雜性的漸近性態(tài)漸近下界記號(hào)

(g(n))={f(n)|存在正常數(shù)c和n0使得對(duì)所有nn0有：0

cg(n)

f(n)}漸近確界記號(hào)⊙

當(dāng)且僅當(dāng)f(n)=O(g(n))且f(n)=(g(n))，定義f(n)=⊙(g(n))。表示f(n)與g(n)同階。632.3時(shí)間復(fù)雜性的漸近性態(tài)非緊上界記號(hào)o若對(duì)于任意正常數(shù)c>0，存在常數(shù)n0>0，當(dāng)n>=n0時(shí)，滿足0f(n)cg(n)，則稱(chēng)f(n)=o(g(n))。非緊下界記號(hào)若對(duì)于任意正常數(shù)c>0，存在常數(shù)n0>0，當(dāng)n>=n0時(shí)，滿足0cg(n)f(n)，則稱(chēng)f(n)=(g(n))。例如，f(n)=12n2+6n=o(n3)=(n)直觀上，o(.)在漸近意義上類(lèi)似于“小于”，(.)在漸近意義上類(lèi)似于“大于”。642.4非遞歸算法分析例1：交換i和j的內(nèi)容Temp=i；i=j；j=temp；以上三條單個(gè)語(yǔ)句的執(zhí)行次數(shù)均為1，該算法段的執(zhí)行時(shí)間是一個(gè)與問(wèn)題規(guī)模n無(wú)關(guān)的常數(shù)。算法的時(shí)間復(fù)雜度為常數(shù)階，記作T(n)=Ο(1)。652.4非遞歸算法分析例2：求數(shù)組最小值

intArrayMin(inta[],intn){min=a[0];for(i=1;i<n;i++)if(a[i]<min)min=a[i];returnmin;}循環(huán)體內(nèi)計(jì)算時(shí)間*循環(huán)次數(shù)。如果循環(huán)變量與問(wèn)題規(guī)模n有關(guān)，則時(shí)間復(fù)雜度一般為O(n)。

662.4非遞歸算法分析例3：嵌套循環(huán)情況(1)x=0；y=0；(2)for(k=1；k<=n；k++)(3)x++；(4)for(i=1；i<=n；i++)(5)for(j=1；j<=n；j++)(6)y++；該算法段的時(shí)間復(fù)雜度為T(mén)(n)=Ο(n2)。當(dāng)有若干個(gè)嵌套循環(huán)語(yǔ)句時(shí)，算法的時(shí)間復(fù)雜度是由嵌套層數(shù)最多的循環(huán)語(yǔ)句中最內(nèi)層語(yǔ)句的執(zhí)行次數(shù)決定的。672.4非遞歸算法分析例4：嵌套循環(huán)情況for(i=1;i<=n;++i)for(j=1;j<=n;++j){c[i,j]=0;for(k=0;k<=n;++k)c[i,j]=c[i,j]+a[i,k]*b[k,j]; }該算法時(shí)間復(fù)雜度為O(n3

)68非遞歸算法的基本法則：順序語(yǔ)句：各語(yǔ)句計(jì)算時(shí)間相加；for/while循環(huán)：循環(huán)體內(nèi)計(jì)算時(shí)間*循環(huán)次數(shù)；嵌套循環(huán)：最深層循環(huán)體內(nèi)計(jì)算時(shí)間*所有循環(huán)次數(shù)；if-else語(yǔ)句：if語(yǔ)句計(jì)算時(shí)間和else語(yǔ)句計(jì)算時(shí)間的較大者。2.4非遞歸算法分析692.5遞歸算法分析遞歸算法：建立遞歸方程;遞推（迭代）求解例1：求n!intfactorial(intn){if(n==0)return1;returnn*factorial(n-1);}70?íì>+==15)2(217)(2nnnTnnT)(2nO=222112222225)2(52)2(52)1(25))2(5))4(5)8(2(2(25))2(5)4(2(25)2(2)(nnnTnnnnTnnnTnnTnTkkk+×′+++=+++=++=+=--L2.5遞歸算法分析例2：71例線性對(duì)數(shù)階O(log2n)：

i=1;

①

while(i<=n)

i=i*2;②解：語(yǔ)句1的頻度是1,

設(shè)語(yǔ)句2的頻度是f(n),

則：2^f(n)<=n;f(n)<=log2n

取最大值f(n)=log2n,

T(n)=O(log2n)72Ο(1)稱(chēng)為常數(shù)級(jí)Ο(logn)稱(chēng)為對(duì)數(shù)級(jí)Ο(n)稱(chēng)為線性級(jí)Ο(nc)稱(chēng)為多項(xiàng)式級(jí)Ο(cn)稱(chēng)為指數(shù)級(jí)Ο(n!)稱(chēng)為階乘級(jí)(n為問(wèn)題的規(guī)模,c為一常量)2.6算法復(fù)雜性的一般表示形式低高時(shí)間復(fù)雜性73提綱一、算法與程序二、算法復(fù)雜性分析三、用C++語(yǔ)言描述算法的方法74用c++描述算法75（1）選擇語(yǔ)句：（1.1)if語(yǔ)句：（1.2)？語(yǔ)句：

if(expression)statement;elsestatement;exp1?exp2:exp3y=x>9?100:200;等價(jià)于：if(x>9)y=100;elsey=200;76（1.3)switch語(yǔ)句：switch(expression){case1:statementsequence;break;case2:statementsequence;break;

default:statement