第1章算法概述1

1、2022-2-261第一章第一章 算法概述算法概述2理解算法的概念。理解算法的概念。理解什么是程序，程序與算法的區(qū)別和內(nèi)在聯(lián)系。理解什么是程序，程序與算法的區(qū)別和內(nèi)在聯(lián)系。掌握算法的計(jì)算復(fù)雜性概念。掌握算法的計(jì)算復(fù)雜性概念。掌握算法漸近復(fù)雜性的數(shù)學(xué)表述。掌握算法漸近復(fù)雜性的數(shù)學(xué)表述。掌握用掌握用C+語言描述算法的方法語言描述算法的方法學(xué)習(xí)要點(diǎn)學(xué)習(xí)要點(diǎn):3一、算法與程序二、算法復(fù)雜性分析三、用C+語言描述算法的方法4一、算法與程序一、算法與程序二、算法復(fù)雜性分析三、用C+語言描述算法的方法5 在中央電視臺幸運(yùn)在中央電視臺幸運(yùn)5252節(jié)目中節(jié)目中, ,有一個(gè)猜商品有一個(gè)猜商品價(jià)格的環(huán)節(jié)價(jià)格的環(huán)節(jié),

2、 ,竟猜者如在規(guī)定的時(shí)間內(nèi)大體猜出竟猜者如在規(guī)定的時(shí)間內(nèi)大體猜出某種商品的價(jià)格某種商品的價(jià)格, ,就可獲得該件商品就可獲得該件商品. .現(xiàn)有一商品現(xiàn)有一商品, ,價(jià)格在價(jià)格在0-80000-8000元之間元之間, ,采取怎樣的策略才能在短采取怎樣的策略才能在短的時(shí)間內(nèi)說出正確的時(shí)間內(nèi)說出正確( (大體上大體上) )的答案呢的答案呢? ?第一步第一步:報(bào)報(bào)“4000”；第二步第二步:若主持人說高了若主持人說高了(說明答案說明答案在在04000之間之間),就報(bào)就報(bào)“2000”,否則否則(答數(shù)在答數(shù)在40008000之間之間)報(bào)報(bào)“6000”；第三步第三步:重復(fù)第二步的報(bào)數(shù)方法取中間重復(fù)第二步的報(bào)數(shù)

3、方法取中間數(shù)數(shù),直至得到正確結(jié)果直至得到正確結(jié)果.6兩個(gè)大人和兩名兒童一兩個(gè)大人和兩名兒童一起渡河，渡口只有一條起渡河，渡口只有一條小船，一次只能渡過一小船，一次只能渡過一個(gè)大人或兩名兒童，他個(gè)大人或兩名兒童，他們四人都會劃船，但都們四人都會劃船，但都不會游泳。請你幫他們不會游泳。請你幫他們設(shè)計(jì)一個(gè)渡河方案。設(shè)計(jì)一個(gè)渡河方案。什么是算法呢？什么是算法呢？第一步：第一步：兩個(gè)小孩同船渡過河去；兩個(gè)小孩同船渡過河去； 第二步：第二步：一個(gè)小孩劃船回來；一個(gè)小孩劃船回來； 第三步：第三步：一個(gè)大人獨(dú)自劃船渡過河去；一個(gè)大人獨(dú)自劃船渡過河去； 第四步：第四步：對岸的小孩劃船回來；對岸的小孩劃船回來；

4、第五步：第五步：兩個(gè)小孩再同船渡過河去；兩個(gè)小孩再同船渡過河去； 第六步：第六步：一個(gè)小孩劃船回來；一個(gè)小孩劃船回來；第七步：第七步：余下的一個(gè)大人獨(dú)自劃船渡過河去；余下的一個(gè)大人獨(dú)自劃船渡過河去； 第八步：第八步：對岸的小孩劃船回來；對岸的小孩劃船回來； 第九步：第九步：兩個(gè)小孩再同船渡過河去。兩個(gè)小孩再同船渡過河去。 7什么是算法呢？什么是算法呢？ 簡單地說，算法就是解決問題的方法或步驟。8你對以下的你對以下的“算法算法”如何理解？如何理解？ 要把大象裝冰箱，分幾步？要把大象裝冰箱，分幾步？答：分三步：答：分三步：第一步：打開冰箱門第一步：打開冰箱門第二步：把大象裝冰箱第二步：把大象裝冰箱

5、第三步：關(guān)上冰箱門第三步：關(guān)上冰箱門問：問：問題問題39 一位商人有一位商人有9 9枚金幣，其中有一枚枚金幣，其中有一枚略輕的假幣，你能用天平（無砝碼）略輕的假幣，你能用天平（無砝碼）將假幣找出來嗎？寫出解決這一問題將假幣找出來嗎？寫出解決這一問題的算法。的算法。第一步：把第一步：把9 9枚金幣平均分成三組，每組三枚。枚金幣平均分成三組，每組三枚。先將其中的兩組放在天平的兩邊，如果天平先將其中的兩組放在天平的兩邊，如果天平不平衡，那么假金幣就在輕的那一組；如果不平衡，那么假金幣就在輕的那一組；如果天平左右平衡，則假金幣就在未稱量的那一天平左右平衡，則假金幣就在未稱量的那一組里。組里。取出含假幣

6、的那一組，從中任取兩枚金幣放取出含假幣的那一組，從中任取兩枚金幣放在天平兩邊進(jìn)行稱量，如果天平不平衡，則在天平兩邊進(jìn)行稱量，如果天平不平衡，則假金幣在輕的那一邊；若平衡，則未稱的那假金幣在輕的那一邊；若平衡，則未稱的那一枚就是假幣。一枚就是假幣。第二步：第二步：第三步：第三步：問題問題410l算法是指解決問題的方法和過程。算法是指解決問題的方法和過程。l算法是對特定問題求解步驟的一種描述，算法是對特定問題求解步驟的一種描述，包含操作的有限規(guī)則和操作的有限序列。包含操作的有限規(guī)則和操作的有限序列。 l通俗一點(diǎn)講，算法就是一個(gè)解決問題通俗一點(diǎn)講，算法就是一個(gè)解決問題的公式（數(shù)學(xué)手冊上的公式都是經(jīng)典

7、算的公式（數(shù)學(xué)手冊上的公式都是經(jīng)典算法）、規(guī)則、思路、方法和步驟。算法可法）、規(guī)則、思路、方法和步驟。算法可以用自然語言描述，也可以用流程圖描述，以用自然語言描述，也可以用流程圖描述，但最終要用計(jì)算機(jī)語言編程，上機(jī)實(shí)現(xiàn)。但最終要用計(jì)算機(jī)語言編程，上機(jī)實(shí)現(xiàn)。 11 從更廣義的角度來看從更廣義的角度來看,并不是只有并不是只有“計(jì)算計(jì)算”的問的問題才有算法題才有算法,日常生活中處處都有日常生活中處處都有.如如樂譜樂譜是樂隊(duì)演是樂隊(duì)演奏的算法奏的算法,菜譜菜譜是做菜肴的算法是做菜肴的算法,珠算口訣珠算口訣是使用算是使用算盤的算法盤的算法. 人們的生產(chǎn)活動和日常生活離不開算法，都在人們的生產(chǎn)活動和日常生

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

9、是若干指令的有窮序列，滿足性質(zhì)：n輸入輸入： 有有1個(gè)或多個(gè)滿足給定約束條件的量作為算法的輸入。個(gè)或多個(gè)滿足給定約束條件的量作為算法的輸入。n輸出輸出： 算法產(chǎn)生至少一個(gè)量作為輸出。算法產(chǎn)生至少一個(gè)量作為輸出。n確定性確定性：組成算法的每條指令是清晰，無歧義的。：組成算法的每條指令是清晰，無歧義的。n有限性有限性：算法中每條指令的執(zhí)行次數(shù)是有限的，執(zhí)行每條指令：算法中每條指令的執(zhí)行次數(shù)是有限的，執(zhí)行每條指令的時(shí)間也是有限的。的時(shí)間也是有限的。l算法要求其執(zhí)行時(shí)間是有限的 (終止性) 。l程序的執(zhí)行時(shí)間可能是無限的。(例操作系統(tǒng)，只要整個(gè)系統(tǒng)不遭破壞，它將永遠(yuǎn)不會停止，即使沒有作業(yè)需要處理，它仍

10、處于動態(tài)等待中。因此，操作系統(tǒng)不是一個(gè)算法。 )13以累加以累加10個(gè)個(gè)1的算法為例的算法為例不正確的算法不正確的算法 (無結(jié)束無結(jié)束)第一步第一步 開始開始第二步第二步 N=0第三步第三步 N=N+1第四步第四步 轉(zhuǎn)第三步轉(zhuǎn)第三步第五步第五步 結(jié)束結(jié)束不正確的算法不正確的算法 (指令不清晰指令不清晰 )第一步第一步 開始開始第二步第二步 N=0第三步第三步 N=N+1第四步第四步 根據(jù)根據(jù)N值值 轉(zhuǎn)第三步或第五步轉(zhuǎn)第三步或第五步 第五步第五步 結(jié)束結(jié)束正確的算法正確的算法 第一步第一步 開始開始 第二步第二步 N=0 第三步第三步 N=N+1 第四步第四步 N9 轉(zhuǎn)第五步轉(zhuǎn)第五步 否則轉(zhuǎn)第三

11、步否則轉(zhuǎn)第三步 第五步第五步 結(jié)束結(jié)束14l程序是某個(gè)算法或過程的在計(jì)算機(jī)上的一程序是某個(gè)算法或過程的在計(jì)算機(jī)上的一個(gè)具體的實(shí)現(xiàn)。個(gè)具體的實(shí)現(xiàn)。l程序是依賴于程序設(shè)計(jì)語言的，甚至依賴程序是依賴于程序設(shè)計(jì)語言的，甚至依賴于計(jì)算機(jī)結(jié)構(gòu)的。于計(jì)算機(jī)結(jié)構(gòu)的。l算法是脫離具體的計(jì)算機(jī)結(jié)構(gòu)和程序設(shè)計(jì)算法是脫離具體的計(jì)算機(jī)結(jié)構(gòu)和程序設(shè)計(jì)語言的。語言的。15l(1).一個(gè)程序不一定滿足有窮性。例操作系統(tǒng)，只要整個(gè)系統(tǒng)不遭破壞，它將永遠(yuǎn)不會停止，即使沒有作業(yè)需要處理，它仍處于動態(tài)等待中。因此，操作系統(tǒng)不是一個(gè)算法。 l(2).程序中的指令必須是機(jī)器可執(zhí)行的，而算法中的指令則無此限制。l (3).算法代表了對問題

12、的解，而程序則是算法在計(jì)算機(jī)上的特定的實(shí)現(xiàn)。一個(gè)算法若用程序設(shè)計(jì)語言來描述，則它就是一個(gè)程序. 16l算法算法程序程序l算法描述：自然語言，流程圖，程序設(shè)計(jì)算法描述：自然語言，流程圖，程序設(shè)計(jì)語言，語言，偽代碼偽代碼l用各種算法描述方法所描述的同一算法，用各種算法描述方法所描述的同一算法，該算法的功用是一樣的，允許在算法的描述該算法的功用是一樣的，允許在算法的描述和實(shí)現(xiàn)方法上有所不同。和實(shí)現(xiàn)方法上有所不同。l本書中采用類本書中采用類C+偽代碼語言描述算法偽代碼語言描述算法171819202122當(dāng)當(dāng)while, 做到做到until (到條件到條件)在在C語言為了簡練語言為了簡練, 沒有沒有un

13、til,只有只有while, 23242526l對算法的學(xué)習(xí)包括五個(gè)方面的內(nèi)容： 設(shè)計(jì)算法。 表示算法。 確認(rèn)算法。 分析算法。 驗(yàn)證算法。27l 設(shè)計(jì)算法。算法設(shè)計(jì)工作是不可能完全自動化的，應(yīng)學(xué)習(xí)了解已經(jīng)被實(shí)踐證明是有用的一些基本的算法設(shè)計(jì)方法，這些基本的設(shè)計(jì)方法不僅適用于計(jì)算機(jī)科學(xué)，而且適用于電氣工程、運(yùn)籌學(xué)等領(lǐng)域；l 表示算法。描述算法的方法有多種形式，例如自然語言和算法語言，各自有適用的環(huán)境和特點(diǎn)；28l確認(rèn)算法。算法確認(rèn)的目的是使人們確信這一算法能夠正確無誤地工作，即該算法具有可計(jì)算性。正確的算法用計(jì)算機(jī)算法語言描述，構(gòu)成計(jì)算機(jī)程序，計(jì)算機(jī)程序在計(jì)算機(jī)上運(yùn)行，得到算法運(yùn)算的結(jié)果；l

14、分析算法。算法分析是對一個(gè)算法需要多少計(jì)算時(shí)間和存儲空間作定量的分析。分析算法可以預(yù)測這一算法適合在什么樣的環(huán)境中有效地運(yùn)行，對解決同一問題的不同算法的有效性作出比較；l 驗(yàn)證算法。用計(jì)算機(jī)語言描述的算法是否可計(jì)算、有效合理，須對程序進(jìn)行測試，測試程序的工作由調(diào)試和作時(shí)空分布圖組成。 29l設(shè)Input和Output是兩個(gè)集合。一個(gè)問題是一個(gè)關(guān)系RInputOutput，Input稱為問題R的輸入集合，Input的每個(gè)元素稱為R的一個(gè)輸入，Output稱為問題R的輸出或結(jié)果集合，Output的每個(gè)元素稱為R的一個(gè)結(jié)果。l一個(gè)算法面向一類問題，而不是僅求解問題的一個(gè)或幾個(gè)實(shí)例實(shí)例。30l例如，排

15、序（SORT）問題定義如下：31a a 0,.,n-10,.,n-1 = 5,2,4,6,1,3= 5,2,4,6,1,3a a 0,.,n-10,.,n-1 = = 5 5, ,2 2,4,6,1,3,4,6,1,3a a 0,.,n-10,.,n-1 = = 2,52,5, ,4 4,6,1,3,6,1,3a a 0,.,n-10,.,n-1 = = 2,4,5,2,4,5,6 6,1,3,1,3a a 0,.,n-10,.,n-1 = = 2,4,5,6,2,4,5,6,1 1,3,3a a 0,.,n-10,.,n-1 = = 1,2,4,5,6,1,2,4,5,6,3 3a a 0

16、0,.,n-1,.,n-1 = 1,2,3,4,5,6= 1,2,3,4,5,6l算法的思想：撲克牌游戲32l1. 從第一個(gè)元素開始，該元素可以認(rèn)為已經(jīng)被排序 l2. 取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描 l3. 如果該元素（已排序）大于新元素，將該元素移到下一位置 l4. 重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置 l5. 將新元素插入到該位置中 l6. 重復(fù)步驟2 33l插入排序算法 34l正確的算法：對于每一個(gè)輸入都最終停止,而且產(chǎn)生正確的輸出。l不正確算法：n不停止(在某個(gè)輸入上)n對所有輸入都停止，但對某輸入產(chǎn)生不正確結(jié)果l近似算法n對所有輸入都停止n產(chǎn)生

17、近似正確的解或產(chǎn)生不多的不正確解l算法正確性證明n證明算法對所有輸入都停止n證明對每個(gè)輸入都產(chǎn)生正確結(jié)果調(diào)試程序調(diào)試程序 程序正確性證明！程序正確性證明！35算法正確性證明的步驟：l初始化n算法在循環(huán)的第一步迭代開始之前，應(yīng)該是正確的。l保持n如果在循環(huán)的某一次迭代開始之前它是正確的，那么，在下一次迭代開始之前，它也應(yīng)該保持正確。l終止n當(dāng)循環(huán)結(jié)束時(shí)，算法也應(yīng)該是正確的。l分析前面插入排序算法的正確性36l如果根據(jù)應(yīng)用領(lǐng)域進(jìn)行分類的話，算法的種類就更多了。每種應(yīng)用領(lǐng)域都會有大量的算法。一些典型的算法包括排序算法、搜索算法、圖論算法、機(jī)器學(xué)習(xí)、加密算法、數(shù)據(jù)壓縮算法、語法分析算法、數(shù)論與代數(shù)算法

18、等。37l1.遞推法 遞推法是利用問題本身所具有的一種遞推關(guān)系求問題解的一種方法。它把問題分成若干步，找出相鄰幾步的關(guān)系，從而達(dá)到目的，此方法稱為遞推法。38l2.遞歸 遞歸指的是一個(gè)過程：函數(shù)不斷引用自身，直到引用的對象已知l3.窮舉搜索法 窮舉搜索法是對可能是解的眾多候選解按某種順序進(jìn)行逐一枚舉和檢驗(yàn)，并從眾找出那些符合要求的候選解作為問題的解。39l4.貪婪法 貪婪法是一種不追求最優(yōu)解，只希望得到較為滿意解的方法。貪婪法一般可以快速得到滿意的解，因?yàn)樗∪チ藶檎易顑?yōu)解要窮盡所有可能而必須耗費(fèi)的大量時(shí)間。貪婪法常以當(dāng)前情況為基礎(chǔ)作最優(yōu)選擇，而不考慮各種可能的整體情況，所以貪婪法不要回溯。4

19、0l5.分治法 把一個(gè)復(fù)雜的問題分成兩個(gè)或更多的相同或相似的子問題，再把子問題分成更小的子問題直到最后子問題可以簡單的直接求解，原問題的解即子問題的解的合并。41l6.動態(tài)規(guī)劃法 動態(tài)規(guī)劃是一種在數(shù)學(xué)和計(jì)算機(jī)科學(xué)中使用的，用于求解包含重疊子問題的最優(yōu)化問題的方法。其基本思想是，將原問題分解為相似的子問題，在求解的過程中通過子問題的解求出原問題的解。動態(tài)規(guī)劃的思想是多種算法的基礎(chǔ)，被廣泛應(yīng)用于計(jì)算機(jī)科學(xué)和工程領(lǐng)域。42l7.迭代法 迭代是數(shù)值分析中通過從一個(gè)初始估計(jì)出發(fā)尋找一系列近似解來解決問題（一般是解方程或者方程組）的過程，為實(shí)現(xiàn)這一過程所使用的方法統(tǒng)稱為迭代法。 43一、算法與程序二、算法

20、復(fù)雜性分析二、算法復(fù)雜性分析三、用C+語言描述算法的方法44l對于給定的問題，起初只是考慮只要找到一個(gè)算法解決該問題就行，而不管該算法花多長時(shí)間或者占用多大的存儲空間。隨著計(jì)算機(jī)技術(shù)的發(fā)展，人們發(fā)現(xiàn)，求解同一個(gè)問題的不同的算法，所需要的運(yùn)行時(shí)間是不同的。例如對排序問題，除了插入排序算法，還有選擇排序、合并排序以及快速排序算法。我們自然會問，哪個(gè)排序算法好呢？怎么樣評價(jià)一個(gè)算法的好壞呢？這就涉及到算法的時(shí)間和空間資源的分析，即算法效率(Efficiency)的分析。 45l算法效率的分析，指的是算法求解一個(gè)問題所需要的時(shí)間和空間。分析一個(gè)算法，意味著預(yù)測該算法解一個(gè)問題時(shí)，需要花費(fèi)多少時(shí)間和空間

21、資源。l空間資源一般指解決一個(gè)問題，需要多大的內(nèi)存、硬盤空間等來存儲輸入輸出數(shù)據(jù)等。時(shí)間資源一般指的是解決一個(gè)問題需要多長的時(shí)間。一般地，對一個(gè)問題，存在不同的求解算法，我們可以根據(jù)算法所需要的時(shí)空資源來確定出其中有效的算法。隨著計(jì)算機(jī)硬件技術(shù)的發(fā)展，現(xiàn)在計(jì)算機(jī)的內(nèi)存和硬盤空間基本上能滿足問題的需要，即空間資源已經(jīng)不是問題，因此，我們分析一個(gè)算法，主要考慮算法的計(jì)算時(shí)間，今后，我們也主要從時(shí)間資源方面對算法進(jìn)行分析，即分析算法有多快。 46 同一問題可用不同算法解決，而一個(gè)算法的質(zhì)量優(yōu)劣將影響到算法乃至程序的效率。算法分析的目的在于選擇合適算法和改進(jìn)算法。一個(gè)算法的評價(jià)主要從時(shí)間復(fù)雜度和空間復(fù)

22、雜度來考慮。 47l算法復(fù)雜性算法復(fù)雜性 = 算法所需要的計(jì)算機(jī)資源算法所需要的計(jì)算機(jī)資源所需資源所需資源量越多則復(fù)雜性越高，反之所需資源量越少則復(fù)量越多則復(fù)雜性越高，反之所需資源量越少則復(fù)雜性越低。其中最為重要的是：雜性越低。其中最為重要的是：l時(shí)間復(fù)雜性時(shí)間復(fù)雜性T(n)；l空間復(fù)雜性空間復(fù)雜性S(n)。l其中其中n是問題的規(guī)模（輸入大小）是問題的規(guī)模（輸入大?。?。一維數(shù)組問題的輸入大小數(shù)組的長度一維數(shù)組問題的輸入大小數(shù)組的長度矩陣問題的輸入大小矩陣問題的輸入大小=矩陣的維數(shù)矩陣的維數(shù)圖論問題的輸入大小圖論問題的輸入大小=圖的邊數(shù)圖的邊數(shù)/結(jié)點(diǎn)數(shù)結(jié)點(diǎn)數(shù)48l算法的復(fù)雜性取決于算法的復(fù)雜性取

23、決于l(1)求解問題的規(guī)模；求解問題的規(guī)模；l(2)具體的輸入數(shù)據(jù)；具體的輸入數(shù)據(jù)；l(3)算法本身的設(shè)計(jì)。算法本身的設(shè)計(jì)。n若若令令N、I、和和A分別表示問題的規(guī)模、具體的分別表示問題的規(guī)模、具體的輸入和算法本身，則輸入和算法本身，則C = F(N, I, A)或或 C = FA(N, I) = F( N, I)49l時(shí)間時(shí)間復(fù)雜性復(fù)雜性T(N, I)的計(jì)算為：的計(jì)算為： n其中：其中：nti為執(zhí)行抽象計(jì)算機(jī)的第為執(zhí)行抽象計(jì)算機(jī)的第i種指令一次所需要的種指令一次所需要的時(shí)間，這里假定抽象計(jì)算機(jī)共有時(shí)間，這里假定抽象計(jì)算機(jī)共有k種指令。種指令。nei(N, I)為經(jīng)過統(tǒng)計(jì)后得到的為經(jīng)過統(tǒng)計(jì)后得

24、到的執(zhí)行抽象計(jì)算機(jī)的執(zhí)行抽象計(jì)算機(jī)的第第i種指令的次數(shù)。種指令的次數(shù)。 kT(N, I) = ti ei(N, I) i = 150算法分析的目的：算法分析的目的：l 設(shè)計(jì)算法設(shè)計(jì)算法設(shè)計(jì)出復(fù)雜性盡可能低的算法設(shè)計(jì)出復(fù)雜性盡可能低的算法l 選擇算法選擇算法在多種算法中選擇其中復(fù)雜性最低者在多種算法中選擇其中復(fù)雜性最低者51l最壞情況最壞情況下的時(shí)間復(fù)雜性 Tmax(n) = max T(I) | size(I)=n l最好情況最好情況下的時(shí)間復(fù)雜性 Tmin(n) = min T(I) | size(I)=n l平均情況平均情況下的時(shí)間復(fù)雜性 Tavg(n) =l 其中其中I是問題的規(guī)模為是問

25、題的規(guī)模為n的實(shí)例，的實(shí)例，p(I)是實(shí)例是實(shí)例I出現(xiàn)的概率出現(xiàn)的概率。nIsizeITIp)()()(52l為了能夠較客觀的反映出一個(gè)算法的效率，在度量為了能夠較客觀的反映出一個(gè)算法的效率，在度量一個(gè)算法的工作量時(shí)，不僅應(yīng)該與所使用的計(jì)算機(jī)、一個(gè)算法的工作量時(shí)，不僅應(yīng)該與所使用的計(jì)算機(jī)、程序設(shè)計(jì)語言以及程序編制者無關(guān)，而且還應(yīng)該與程序設(shè)計(jì)語言以及程序編制者無關(guān)，而且還應(yīng)該與算法實(shí)現(xiàn)過程中的許多細(xì)節(jié)無關(guān)。為此，可以用算算法實(shí)現(xiàn)過程中的許多細(xì)節(jié)無關(guān)。為此，可以用算法在執(zhí)行過程中所需基本運(yùn)算的執(zhí)行次數(shù)來度量算法在執(zhí)行過程中所需基本運(yùn)算的執(zhí)行次數(shù)來度量算法的工作量?；具\(yùn)算反映了算法運(yùn)算的主要特征，

26、法的工作量?；具\(yùn)算反映了算法運(yùn)算的主要特征，因此，用基本運(yùn)算的次數(shù)來度量算法工作量是客觀因此，用基本運(yùn)算的次數(shù)來度量算法工作量是客觀的也是實(shí)際可行的，有利于比較同一問題的幾種算的也是實(shí)際可行的，有利于比較同一問題的幾種算法的優(yōu)劣。法的優(yōu)劣。l例如，在考慮兩個(gè)矩陣相乘時(shí)，可以將兩個(gè)實(shí)數(shù)之例如，在考慮兩個(gè)矩陣相乘時(shí)，可以將兩個(gè)實(shí)數(shù)之間的乘法運(yùn)算作為基本運(yùn)算間的乘法運(yùn)算作為基本運(yùn)算.53l在一般的計(jì)算機(jī)系統(tǒng)中，基本的運(yùn)算和操作有以下四類：算術(shù)運(yùn)算：主要包括加、減、乘、除等運(yùn)算。邏輯運(yùn)算：主要包括“與”、“或”、“非”等運(yùn)算。關(guān)系運(yùn)算：主要包括“大于”、“小于”、“等于”、“不等于”等運(yùn)算。數(shù)據(jù)傳輸

27、：主要包括賦值、輸入、輸出等操作。n規(guī)定其中每條指令所需的時(shí)間都為常量。算法的執(zhí)行時(shí)間算法的執(zhí)行時(shí)間= 原子操作的執(zhí)行次數(shù)原子操作的執(zhí)行次數(shù)原子操作的執(zhí)行時(shí)間原子操作的執(zhí)行時(shí)間54 template void InsertionSort(Type *a, int n) Type key; / cost times for (int i = 1; i =0 & ajkey ) / c4 sum of ti aj+1=aj; / c5 sum of (ti-1) j-; / c6 sum of (ti-1) aj+1=key; / c7 n-1 55l在最好情況下，ti=1, for 1

28、i n;l在最壞情況下，ti i+1, for 1 i 0，存在常數(shù)n00，當(dāng)n=n0時(shí)，滿足0 f(n) cg(n)，則稱f(n)=o(g(n)。l非緊下界記號非緊下界記號 若對于任意正常數(shù)c0，存在常數(shù)n00，當(dāng)n=n0時(shí)，滿足0 cg(n) f(n) ，則稱f(n)= (g(n)。l例如，f(n)=12n2+6n=o(n3)=(n)l直觀上，o(.)在漸近意義上類似于“小于”，(.)在漸近意義上類似于“大于” 。65例1：交換i和j的內(nèi)容 Temp=i；i=j；j=temp； 以上三條單個(gè)語句的執(zhí)行次數(shù)均為1，該算法段的執(zhí)行時(shí)間是一個(gè)與問題規(guī)模n無關(guān)的常數(shù)。算法的時(shí)間復(fù)雜度為常數(shù)階，記作

29、T(n)=(1)。66例2：求數(shù)組最小值 int ArrayMin(int a , int n) min=a0; for (i=1; in; i+) if (aimin) min=ai; return min; 循環(huán)體內(nèi)計(jì)算時(shí)間*循環(huán)次數(shù)。如果循環(huán)變量與問題規(guī)模n有關(guān)，則時(shí)間復(fù)雜度一般為O(n)。 67例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(n)=(n2)。 當(dāng)有若干個(gè)嵌套循環(huán)語句時(shí)，算法的時(shí)間復(fù)雜度是由嵌套層數(shù)

30、最多的循環(huán)語句中最內(nèi)層語句的執(zhí)行次數(shù)決定的。68例4：嵌套循環(huán)情況for(i=1;i=n;+i) for(j=1;j=n;+j) ci,j=0; for(k=0;k=n;+k) ci,j= ci,j+ai,k*bk,j; 該算法時(shí)間復(fù)雜度為O(n3 )69非遞歸算法的基本法則：非遞歸算法的基本法則：l順序語句： 各語句計(jì)算時(shí)間相加；lfor / while 循環(huán)：循環(huán)體內(nèi)計(jì)算時(shí)間*循環(huán)次數(shù)；l嵌套循環(huán)： 最深層循環(huán)體內(nèi)計(jì)算時(shí)間*所有循環(huán)次數(shù)；lif-else語句： if語句計(jì)算時(shí)間和else語句計(jì)算時(shí)間的較大者。70遞歸算法：遞歸算法：建立遞歸方程建立遞歸方程;遞推（迭代）求解遞推（迭代）求解

31、例例1：求：求n!int factorial(int n) if (n = 0) return 1; return n*factorial(n-1); 0) 1 () 1(0) 1 ()(nOnTnOnT nOnT)(71 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 LL例2：72 i=1; l while (i=n)l i=i*2; l解： 語句1的頻度是1, l 設(shè)語句2的頻度是f(n), 則：2f(n)=n;f(n)

32、9 ? 100:200; 等價(jià)于： if (x9) y=100; else y=200;77switch (expression) case 1: statement sequence; break; case 2: statement sequence; break; default: statement sequence; 78l（2.1) for 循環(huán)：循環(huán)：l for (init;condition;inc) statement;l（2.2) while 循環(huán)：循環(huán)：l while (condition) statement;l（2.3) do-while 循環(huán)：循環(huán)： l dol statement;l while (