第1章算法概述1

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

DesignandAnalysisofComputerAlgorithms

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

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

10從更廣義的角度來看,并不是只有“計算”的問題才有算法,日常生活中處處都有.如樂譜是樂隊演奏的算法,菜譜是做菜肴的算法,珠算口訣是使用算盤的算法.

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

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

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

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

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

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

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

372.遞歸

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

3.窮舉搜索法

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

384.貪婪法

貪婪法是一種不追求最優(yōu)解，只希望得到較為滿意解的方法。貪婪法一般可以快速得到滿意的解，因為它省去了為找最優(yōu)解要窮盡所有可能而必須耗費的大量時間。貪婪法常以當(dāng)前情況為基礎(chǔ)作最優(yōu)選擇，而不考慮各種可能的整體情況，所以貪婪法不要回溯。

395.分治法

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

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

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

417.迭代法

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

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

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

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

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

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

②邏輯運算：主要包括“與”、“或”、“非”等運算。

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

④數(shù)據(jù)傳輸：主要包括賦值、輸入、輸出等操作。規(guī)定其中每條指令所需的時間都為常量。算法的執(zhí)行時間=原子操作的執(zhí)行次數(shù)×原子操作的執(zhí)行時間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時間復(fù)雜性計算54在最好情況下，ti=1,for1

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

i+1,for1

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

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

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

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

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

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

cg(n)

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

當(dāng)且僅當(dāng)f(n)=O(g(n))且f(n)=(g(n))，定義f(n)=⊙(g(n))。表示f(n)與g(n)同階。632.3時間復(fù)雜性的漸近性態(tài)非緊上界記號o若對于任意正常數(shù)c>0，存在常數(shù)n0>0，當(dāng)n>=n0時，滿足0f(n)cg(n)，則稱f(n)=o(g(n))。非緊下界記號若對于任意正常數(shù)c>0，存在常數(shù)n0>0，當(dāng)n>=n0時，滿足0cg(n)f(n)，則稱f(n)=(g(n))。例如，f(n)=12n2+6n=o(n3)=(n)直觀上，o(.)在漸近意義上類似于“小于”，(.)在漸近意義上類似于“大于”。642.4非遞歸算法分析例1：交換i和j的內(nèi)容Temp=i；i=j；j=temp；以上三條單個語句的執(zhí)行次數(shù)均為1，該算法段的執(zhí)行時間是一個與問題規(guī)模n無關(guān)的常數(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)計算時間*循環(huán)次數(shù)。如果循環(huán)變量與問題規(guī)模n有關(guān)，則時間復(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++；該算法段的時間復(fù)雜度為T(n)=Ο(n2)。當(dāng)有若干個嵌套循環(huán)語句時，算法的時間復(fù)雜度是由嵌套層數(shù)最多的循環(huán)語句中最內(nèi)層語句的執(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]; }該算法時間復(fù)雜度為O(n3

)68非遞歸算法的基本法則：順序語句：各語句計算時間相加；for/while循環(huán)：循環(huán)體內(nèi)計算時間*循環(huán)次數(shù)；嵌套循環(huán)：最深層循環(huán)體內(nèi)計算時間*所有循環(huán)次數(shù)；if-else語句：if語句計算時間和else語句計算時間的較大者。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例線性對數(shù)階O(log2n)：

i=1;

①

while(i<=n)

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

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

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

取最大值f(n)=log2n,

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

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

default:statement