大學計算機第7講-算法程序與計算系統(tǒng)之靈魂

1、第7講統(tǒng)進行問題求解的關鍵是發(fā)現(xiàn)、構造與設計求解問題的算法。理解：構造與設計任何一個算法要經過哪些步驟，在每一步驟中要做哪些事情？算法是計算學科和計算系統(tǒng)的，各學科利用計算系內容提要2/55基本目標: 理解算法類問題求解框架SpecificGeneralCourse具體實例一般過程課程算法類問題數學建模數學建模，離散數學(集合論與圖論、數理邏輯)等問題算法策略設計求解的數據結構設計過+算法與數據結構程算法過程(控及制結構)設計思維方程序設計語言及高級語言程序設計法算法實現(xiàn)復雜性TSP貪心算法程序（C語言）TSP問題貪心算法過程設計TSP問題貪心算法數據結構設計求解TSP問題的算法策略設計貪心T

2、SP問題數學模型TSP問題3/551. 算法與算法類問題求解算法與算法類問題求解-什么是算法-算法類問題及求解概述4/551.1 什么是算法?算法u 算法-計算學科和計算?！八惴ā?Algorithm)一詞源于數學家的名字：公元825年，的數學家阿科瓦里茨米(AlKhowarizmi)寫了著名的波斯教科書(Persian Textbook)，書中概括了進行四則算術運算的計算規(guī)則。u 算法是一個有窮規(guī)則的集合，它用規(guī)則規(guī)定了解決某一特定類型問題的運算序列，或者規(guī)定了任務執(zhí)行或問題求解的一系列步驟。如音樂樂譜、太極拳譜等都可看作廣義的算法5/551.2 為什么算法很重要呢?算法、語言與計算機程序步

3、驟書寫的規(guī)范、語則、標準的集合是人和計算機都能理解的語言計算機語言算法程序解決問題的步驟計算機能夠理解與執(zhí)行的解決問題的步驟“是否會編程序”，本質上是“能否想出求解問題的算法”，其次才是將算法用計算機可以識別的形式書寫出來1. 算法與算法類問題求解1.3 什么是計算學科中的算法?6/55算法示例u 歐幾里德算法：求解兩個數的最大公約數的算法(公元前300年)ü 表述了最大公約數的求解過程ü 表述了一個判定過程，即判定“m和n是互質的”（即除1以外，m和n沒有公約數）命題的真假。ü 該算法體現(xiàn)了輸入、輸出、有窮規(guī)則、確定性和能行性等算法的基本特征。尋找兩個正整數的最

4、大公約數的歐幾里德算法輸入：正整數M和正整數N輸出：M和N的最大公約數(設M>N) 算法步驟：Step 1. M除以N,記余數為RStep 2. 如果R不是0，將N的值賦給M, R的值賦給N, 返回Step 1; 否則, 最大公約數是N, 輸出N, 算法結束。7/551.4 具備什么特征才能被認為是算法?算法的基本特征ü 有窮性：一個算法在執(zhí)行有窮步規(guī)則之后必須結束。ü 確定性：算法的每一個步驟必須要確切地定義，不得有歧義性。ü 輸入：算法有零個或多個的輸入。ü 輸出：算法有一個或多個的輸出/結果，即與輸入有某個特定關系的量。ü 能行性：

5、算法中有待執(zhí)行的運算和操作必須是相當基本的(可以由時間內完成。自動完成)。并能在有限 典型的“重復/循環(huán)”與“迭代”基本運算：除法、賦值、邏輯判斷尋找兩個正整數的最大公約數的歐幾里德算法輸入：正整數M和正整數N輸出：M和N的最大公約數(設M>N) 算法步驟：Step 1. M除以N,記余數為RStep 2. 如果R不是0，將N的值賦給M, R的值賦給N, 返回Step 1; 否則, 最大公約數是N, 輸出N, 算法結束。8/551.5 你知道一些典型的算法類問題嗎?算法類問題：由一個算法可以解決的問題u 算法(類)問題：尋找一個(唯一的)方法(算法)以解決同一類型的無窮多個單個問題系列的

6、問題。u 典型問題：ü 哥尼斯堡七橋問題：“尋找走遍這7座橋且只許走過每座橋一次最后又回到原出發(fā)點的路徑”“對給定的任意一個河道圖與任意多座橋判定 可能不可能每座橋恰好走過一次?”。ü 梵天塔問題：有三根柱子，梵天將64個直徑大小不一的金盤子按照從大到小的順序依次套放 在第一根柱子上形成一座金塔，要求每次只能移動 一個盤子，盤子只能在三根柱子上來回移動不能放 在他處，在移動過程中三根柱子上的盤子必須始終 保持大盤在下小盤在上。ü 其他如：背包問題，丟番圖方程可解性問題；9/551.6 你知道TSP問題嗎?算法類問題示例u TSP問題(Traveling Sales

7、man Problem，旅行商問題)，威廉哈密爾頓爵士和英國數學家克克曼T.P.Kirkman于19世紀初提出TSP問題u TSP問題：有若干個城市，任何兩個城市之間的距離都是確定的，現(xiàn)要 求一旅行商從某城市出發(fā)必須經過每一個城市且只能在每個城市逗留一次， 最后回到原出發(fā)城市，問如何事先確定好一條最短的路線使其旅行的費用最少。u TSP是最有代表性的組合優(yōu)化問題之一，在半導體制造(線路規(guī)劃)、物流運輸(路徑規(guī)劃)等行業(yè)有著廣泛的應用。城市之間的距離10/551.7 你知道算法類問題求解的一般步驟嗎?算法類問題求解框架u 問題抽象及數學建模：將問題抽象為一個數學問題，并給出求解該數學問題的算法模

8、型。u 算法策略設計u 算法的數據結構和控制結構設計：將數學模型轉換為可由計算機自動計算的算法。u 算法的實現(xiàn)：用程序設計語言編寫算法實現(xiàn)的程序。u 算法的分析：分析算法的正確性和復雜性，判斷能行性！SpecificGeneralCourse具體實例一般過程課程算法類問題數學建模數學建模，離散數學(集合論與圖論、數理邏輯)等問題算法策略設計求解的數據結構設計過+算法與數據結構程算法過程(控及制結構)設計思維方程序設計語言及高級語言程序設計法算法實現(xiàn)復雜性TSP貪心算法程序（C語言）TSP問題貪心算法過程設計TSP問題貪心算法數據結構設計求解TSP問題的算法策略設計貪心TSP問題數學模型TSP問

9、題11/552. 數學建模與算法策略設計-算法思想數學建模與算法策略設計-算法思想-數學建模-有不同的算法求解策略2. 數學建模與算法策略設計-算法思想2.1 為什么說數學建模對于算法很重要?12/55算法類問題求解的第一步就是要數學建模。u 數學建模：是一種數學的思考方法，是運用數學的語言和方法，通過抽象、簡化建立對問題進行精確描述和定義的數學模型。簡單而言，數學建模是用數學語言描述實際現(xiàn)象的過程，即建立數學模型的過程。u 數學模型是對實際問題的一種數學表述，是關于部分現(xiàn)實世界為某種目的的一個抽象的簡化的數學結構。將現(xiàn)實世界的問題抽象成數學模型，就可能發(fā)現(xiàn)問題的本質及其能否求解，甚至找到求解

10、該問題的方法和算法。2. 數學建模與算法策略設計-算法思想2.1 為什么說數學建模對于算法很重要?13/55哥尼斯堡七橋問題被抽象成一個“圖(Graph)”-由節(jié)點和邊所構成的一種結構，-依據“圖”，可發(fā)現(xiàn)該問題所蘊含的許多性質：u “回路-從一個節(jié)點出發(fā)最后又回到該節(jié)點的一條路徑”u “連通兩個節(jié)點間有路徑相連接”u “可達從一個節(jié)點出發(fā)能夠到達另一個節(jié)點”u “經過圖中每邊一次且僅一次的回路”u “經過圖中每個節(jié)點一次且僅一次的回路”u 什么情況下有解，什么情況下無解？u 注：離散數學或者集合論與圖論課程將介紹圖的有關性質和方法。如果能抽象成數學模型，則可將一個具體問題的求解，推廣為一類問

11、題的求解！2.數學建模與算法策略設計-算法思想2.2 數學建模要做到怎樣?14/55TSP問題的數學模型2.數學建模與算法策略設計-算法思想2.3 算法思想或者算法策略對問題求解有什么影響?15/55算法策略設計-算法思想當數學建模完成后，就要設計算法的策略或者說問題求解的策略。u TSP問題的基本求解策略u 遍歷：列出每一條可供選擇的路線，計算出每條路線的總里程，最后從中選出一條最短的路線。u 出現(xiàn)的問題是：組合ü 路徑組合數目：(n-1)!ü 20個城市，遍歷總數1.216×1017ü 計算機以每秒檢索1000萬條路線的計算所有路徑組合及其長度速度，

12、需386年。城市之間的距離2.數學建模與算法策略設計-算法思想2.3 算法思想或者算法策略對問題求解有什么影響?16/55u TSP問題的難解性：隨著城市數量的上升，TSP問題的“遍歷”方法計算量劇增，計算將難以承受。u 2001年解決了德國15112個城市的TSP問題，使用了美國Rice大學和普林斯頓大學之間Alpha 處理器組成的110臺計算機，所有計互連的、速度為500MHz 的CompaqEV6算機花費的時間之和為22.6年。AnoptimalTSPtourthrough largest cities. It is theGermanys 15shortest among 43 589

13、 145 600 possible tours visiting each city exactly once.2.數學建模與算法策略設計-算法思想2.4 有哪些算法策略?17/55算法策略設計-算法思想u TSP問題，有沒有其他求解算法呢？u 最優(yōu)解 vs. 可行解u 不同的算法設計策略：ü 遍歷、搜索算法ü 分治算法ü 貪心算法ü 動態(tài)規(guī)劃算法ü u 可選取一種合適的策略來求解TSP問題最優(yōu)解可行解TSP問題的可行解與最優(yōu)解示意2.數學建模與算法策略設計-算法思想2.5 為什么稱為“貪心算法”?18/55貪心算法城市之間的距離u 貪心算法是

14、一種算法策略，或者說問題求解的策略?；舅枷搿敖癯芯平癯怼薄?#252; 一定要做當前情況下的最好選擇，否則將來可能會后悔，故名“貪心”。u TSP問題的貪心算法求解思想ü 從某一個城市開始，每次選擇一個城市，直到所有 城市都被走完。ü 每次在選擇下一個城市的時候，只考慮當前情況，保證迄今為止經過的路徑總距離最短。026813AAAAABBBBCCCDDA(a)(b)(c)(d)(e)19/553.算法設計-算法思想的精確表達算法設計-算法思想的精確表達(I)-算法的數據結構設計-算法的控制結構設計及其表達方法-TSP算法解讀3. 算法設計-算法思想的精確表達3.1 算

15、法設計包括什么?20/55算法設計n 算法的數據結構設計-問題或算法相關的數據之間的邏輯關系及關系的設計 如何將數學模型中的數據轉為計算機可以和處理的數據？ n 算法的控制結構設計-算法的計算規(guī)則或計算步驟設計 如何構造和表達處理的規(guī)則，以便能夠按規(guī)則逐步計算出結果?3. 算法設計-算法思想的精確表達3.2 什么是數據結構?21/55數據結構u 如何組織、記憶、改變和操作數據的集合呢？數據存在什么結構呢？ü 數據的邏輯結構：數據之間的關系；數學模型中反映的通常是數據的邏輯結構。ü 數據的的有順序結構：在反映數據邏輯關系的原則下，數據在器中的方式。典型結構和鏈式結構。結構的基

16、本運算：(1)建立數據結構；(2)清除數據結構；(3)ü 面向數據數據元素；(4)刪除數據元素；(5)更新數據元素；(6)查找數據元素；(7)按序重新排列；(8)判定某個數據結構是否為空，或是否已達到最大允許的容量；(9)統(tǒng)計數據元素的個數等。u 數據結構是數據的邏輯結構、結構及其操作的總稱，它提供了問題求解/算法的數據機制。3. 算法設計-算法思想的精確表達3.2 什么是數據結構?22/55數據結構的設計典型的數據結構- “樹”示例結構中, 用一個指針表達數據之間的邏輯關系數據的結構數據元素對應數據元素的指針指向該元素的父元素數據的邏輯結構1601207030150501003.

17、算法設計-算法思想的精確表達3.2 什么是數據結構?23/55數據結構的設計通過指針的變化, 不改變數據的, 但卻改變了數據之間的邏輯關系數據的結構數據的邏輯結構70301003. 算法設計-算法思想的精確表達3.3 同樣的邏輯結構可以有不同的24/55結構嗎?數據結構的設計數據的結構典型的數據結構- “樹”示例數據元素結構, 用兩個指針另一種表達數據之間的邏輯關系對應數據元素的指針指向該元的左側子結點對應數據元素的指針指向該元的右側子結點數據的邏輯結構數據結構不同，數據之間的操作方法也是不同的7030100左素右素3. 算法設計-算法思想的精確表達3.3 同樣的邏輯結構可以有不同的25/55

18、結構嗎?數據結構的設計典型的數據結構- “樹”示例結構, 用兩個指針(左指針和右指針)表達數據之間的邏輯關系另一種 動手練習一下Null數據的邏輯結構數據的邏輯結構703070301101001003. 算法設計-算法思想的精確表達3.4 多元素變量結構是怎樣的?26/55多元素變量及其程序處理(前講介紹的)u 向量或列表或數組。列M2,3u 矩陣或表12341向量實例2表實例行34Sum=0;For I =1 to 4 Step 1n = 4;Sum=0;For J =0 to n Step 1For J =1 to 4 Step 1 Sum = Sum + MIJ;Next JSum =

19、Sum + mark J ;Next JAvg = Sum/n;Next IAvg = Sum/16;11252225453984421280100348375163. 算法設計-算法思想的精確表達3.5 一個問題中應該設計哪些數據結構?27/55TSP問題的數據結構設計u 數據結構設計就是針對選定的算法策略，設計其相應的數據結構及其運算規(guī)則。不同的算法可能有不同的數據結構及其運算規(guī)則！為編號: A-1, B-2, C-3, D-4城市城市間距離關系: 表或二維數組D，用Dij或Di,j來確定欲處理的每一個元素DD23路徑/解: 一維數組S，用Sj來確定每一個元素SA->D->C-

20、>B->AS1S2S3S4143228/553.算法設計-算法思想的精確表達算法設計-算法思想的精確表達(II)-算法的數據結構設計-算法的控制結構設計及其表達方法-TSP算法解讀3. 算法設計-算法思想的精確表達3.6 怎樣表達算法的步驟呢?29/55算法與程序的基本控制結構ü 順序結構：“”，是按順序執(zhí)行一條條規(guī)則的一種結構 。ü 分支結構：“” ，Q是某些邏輯條件，即按條件判斷結果決定執(zhí)行哪些規(guī)則的一種結構 。ü 循環(huán)結構：控制指令或規(guī)則的多次執(zhí)行的一種結構-迭代(iteration)u 循環(huán)結構又分為有界循環(huán)結構和條件循環(huán)結構。ü 有

21、界循環(huán)： “”，其中N是一個整數。ü 條件循環(huán)：某些時候稱為循環(huán)，“”或”，其中Q是條件?！爱擰成立時反復執(zhí)行A重復執(zhí)行A直到條件Q成立執(zhí)行A指令N次如果Q成立，那么執(zhí)行A，否則執(zhí)行B執(zhí)行A，然后執(zhí)行B3. 算法設計-算法思想的精確表達3.7 怎樣繪制流程圖?30/55算法與程序構造的表達方法：程序流程圖流程圖的基本表示符號ü 矩形框：表示一組順序執(zhí)行的規(guī)則或者程序語句。ü 菱形框：表示條件判斷，并根據判斷結果執(zhí)行不同的分支。ü 圓形框：表示算法或程序的開始或結束。ü 箭頭線：表示算法或程序的。矩形框表示一組順序執(zhí)行的語句菱形框表示判斷語句，決

22、定下一步程序的圓形框表示程序的起始和結束帶箭頭的線段表示程序的3. 算法設計-算法思想的精確表達3.7 怎樣繪制流程圖?31/55算法與程序構造的表達方法：程序流程圖開始u 三種控制結構的流程圖表示方法示意開始開始否循環(huán)控制條件成立？是否條件成立否？是需循環(huán)執(zhí)行的規(guī)則或語句。即：循環(huán)體循環(huán)結束修改部分結束結束結束順序結構的流程圖分支結構的流程圖循環(huán)結構的流程圖第n條規(guī)則或語句條件成立時執(zhí)行的規(guī)則或語句條件不成立時執(zhí)行的規(guī)則或語句第1條規(guī)則或語句初始化部分3. 算法設計-算法思想的精確表達3.7 怎樣繪制流程圖?32/55算法與程序構造的表達方法：程序流程圖開始u 循環(huán)結構的兩種情況的流程圖表示

23、方法示意開始循環(huán)未結束否循環(huán)控制條件成立？是循環(huán)控制條件成立？循環(huán)結束需循環(huán)執(zhí)行的規(guī)則或語句是否修改部分結束有界循環(huán)結構的流程圖(循環(huán)次數確定)條件循環(huán)結構的流程圖(循環(huán)次數不確定)結束修改部分初始化部分需循環(huán)執(zhí)行的規(guī)則或語句初始化部分算法與程序構造的表達方法：程序流程圖u 算法思想及算法流程圖表示示例u 歐幾里德算法流程圖3. 算法設計-算法思想的精確表達33/553.7 怎樣繪制流程圖?開始否r=0?是結束輸出n將n置換為m，r 置換為n以n除m，并令所得余數為r3. 算法設計-算法思想的精確表達3.8 自然語言表述算法有什么問題?34/55算法與程序構造的表達方法：步驟描述法u 步驟描述

24、法，即用人們日常使用的語言和數學語言描述算法的步驟。u 例如：sum=1+2+3+4+n求和問題的算法描述自然語言表示的算法容易出現(xiàn)二義性、不確定性等問題Start of the algorithm(算法開始)(1) 輸入N的值；(2) 設 i 的值為1；sum的值為0；(3) 如果 i<=N，則執(zhí)行第(4)步，否則轉到第(7)步執(zhí)行； (4)計算 sum + i，并將結果賦給sum；(5)計算 i+1，并將結果賦給i; (6)返回到第3步繼續(xù)執(zhí)行； (7)輸出sum的結果。End of the algorithm(算法結束)35/553.算法設計-算法思想的精確表達算法設計-算法思想的

25、精確表達(III)-算法的數據結構設計-算法的控制結構設計及其表達方法-TSP算法解讀3. 算法設計-算法思想的精確表達3.9 算法的控制結構如何設計?36/55開始求解TSP問題的遍歷算法ü 遍歷所有的組合路徑；ü 累加一條路徑的距離之和；ü 判斷某條路徑的距離是不是比當前最短路徑距離短；ü 如果是，則用新路徑取代當前將思想/策略轉變?yōu)椤安襟E”最短路徑，并其距離；比當前最短距離小嗎？否ü 直到所有路徑比較完畢；u 是將該路徑為當前最短路徑，并用其距離值更新當前最短距離是否所有路徑組合完畢否？結束輸出當前最短路徑及當前最短距離組合一條新路徑并計

26、算該路徑的距離當前最短路徑設為空，當前最短距離設為最大值3. 算法設計-算法思想的精確表達3.9 算法的控制結構如何設計?37/55步驟描述法表示的求解TSP問題的貪心算法ü 城市用數字編號來表示,1,2,Nü 任何兩個城市的距離中在數組Di,jü 依次在S1,的城市記過的城市編號被S2, , SN中,即第i 次錄在Si中。ü Step(1)：從第1個城市開始將城市編號1賦值給S1。起，ü Step(6)：第I次的城市為城市j，其距第I-1次城市的距離最短。Start of the Algorithm(1) S1=1;(2) Sum=0;(3)

27、 初始化距離數組DN, N; (4) I=2;(5) 從所有未過的城市中查找距離SI-1最近的城市j;(6) SI=j;(7) I=I+1;(8) Sum=Sum+Dtemp;(9) 如果I<=N，轉步驟(5)，否則，轉步驟(10);(11) Sum=Sum+D1, j；(12) 逐個輸出SN中的全部元素; (13)輸出Sum。End of the Algorithm3. 算法設計-算法思想的精確表達3.9 算法的控制結構如何設計?38/55步驟描述法表示的求解TSP問題的貪心算法(Cont.)u 前述第5步“從所有未一步細化過的城市中查找距離SI-1最近的城市j”還是不夠明確，需要進(

28、5.1)K=2;(5.2)將Dtemp設為一個大數(比所有兩個城市之間的距離都大)(5.3)L=1；(5.4)如果SL=K，轉步驟5.8；/該城市已出現(xiàn)過，跳過(5.5)L=L+1；(5.6)如果L<I，轉5.4；(5.7)如果DK,SI-1<Dtemp; j=K; DtempDK,SI-1；(5.8)K=K+1;(5.9)如果K<=N，轉步驟5.3。3. 算法設計-算法思想的精確表達3.9 算法的控制結構如何設計?39/55流程圖表示的求解TSP問題的貪心算法3. 算法設計-算法思想的精確表達3.10 你能夠讀懂流程圖嗎?40/55算法思想解讀u 計算學科的學生不僅能夠設計

29、算法，而且會描述和表達算法，更要能讀懂算法。內層循環(huán)，L從1至I-1, 循環(huán)判斷第K個城市是否是已過的城市，如是則不參加最小距離的比較；中層循環(huán), K從第2個城市至第N個城市循環(huán), 判斷DK, SI-1是否是最小值，j了最小距離的城市號K。外層循環(huán)，I從2至N循環(huán)；I-1個城市過，正在找與第I-1個城市最 已近距離的城市；已在S中。過的城市號41/554.算法實現(xiàn)-程序設計算法實現(xiàn)-程序設計4. 算法實現(xiàn)-程序設計4.1 算法實現(xiàn)要選定計算機語言，42/55?算法的實現(xiàn)u 程序是算法的一種相容(Compatible)的表示，是利用計算機程序設計語言對算法描述的結果，是可以在計算機上執(zhí)行的算法。

30、u 計算機語言是書寫算法步驟地規(guī)范、標準、語則等，以便使人和計算機能夠理解用計算機語言編寫出的程序(注：更重要的是使計算機能夠理解)。4. 算法實現(xiàn)-程序設計4.1 算法實現(xiàn)要選定計算機語言，43/55?算法的實現(xiàn)u 程序設計過程：一般經過編輯源程序è編譯èè執(zhí)行。所謂編輯源程序是利用程序編輯器，按照計算機語言的規(guī)范書寫程序的過程；所謂編譯是將編制好的源程序代碼程序(又稱為目標代碼)的過程。所謂翻譯成可以執(zhí)行的是將目標代碼與公用函數庫中的函數實現(xiàn)代碼集成起來形成最終可執(zhí)行程序的過程。所謂執(zhí)行就是程序的運行過程。u 計算機語言程序設計環(huán)境通常由一套書寫程序的語則、一

31、個編譯程序、一個程序和一組編譯好的公用函數庫構成。有些計算機語言同時也提供了相應的編程環(huán)境、調試環(huán)境及集成開發(fā)環(huán)境等。4. 算法實現(xiàn)-程序設計44/554.2 你能用某一種計算機語言書寫出TSP問題貪心算法的程序嗎?算法的實現(xiàn)TSP 問題貪心算法程序實例45/555.高級問題初探: 算法分析與計算復雜性高級問題初探:算法分析與計算復雜性5. 高級問題初探: 算法分析與計算復雜性5.1 算法是正確的嗎?46/55算法分析與計算復雜性算法是正確的嗎? uu 算法的正確性問題：ü 問題求解的過程、方法算法是正確的嗎？算法的輸出是問題的解嗎？ü 20世紀60年代，美國一架發(fā)往金星的

32、航天飛機由于控制程序出錯而u 算法的效果評價：ü 算法的輸出是最優(yōu)解還是可行解？如果是可行解，與最優(yōu)解的偏差多大？u 兩種評價方法：ü 證明方法：利用數學方法證明；丟失在太空中ü分析方法：產生或選取大量的、具有代表性的問題實例，利用該算法對這些問題實例進行求解，并對算法產生的結果進行統(tǒng)計分析。算法獲得的解是最優(yōu)的嗎?5. 高級問題初探: 算法分析與計算復雜性5.1 算法是正確的嗎?47/55算法分析與計算復雜性算法分析示例：TSP問題貪心u TSP問題貪心算法的正確性評價：ü 直觀上只需檢查算法的輸出結果中，每個城市出現(xiàn)且僅出現(xiàn)一次，該結果即是TSP問題

33、的可 行解，說明算法正確地求解了這些問題實例u TSP問題貪心算法的效果評價：ü 如果實例的最優(yōu)解已知（問題規(guī)模小或問題已被成功求解），利用統(tǒng)計方法對若干問題實例 的算法結果與最優(yōu)解進行對比分析，即可對其進行效果評價；ü 對于較大規(guī)模的問題實例，其最優(yōu)解往往是未知的，因此，算法的效果評價只能借助于與前人算法結果的比較。5.高級問題初探: 算法分析與計算復雜性5.2 算法的計算時間有多長?48/55算法分析與計算復雜性算法獲得結果的時間有多長?u 另一個問題：算法是能夠執(zhí)行的嗎？u 分析u 算法的效率：時間效率和空間效率u 時間復雜性:如果一個問題的規(guī)模是n，解這一問題的某一算法所需要的時間為T(n)，它是n的某一函數，T(n)稱為這一算法的“時間復雜性”。u “大O記法”：ü 基本參數 n問題實例的規(guī)模ü 把復雜性或運行時間表達為n的函數。ü “O”表示量級 (order)，允許使用“=”代替“”，如n2+n+1 =(n2) 。u 算法的空間復雜度：算法在執(zhí)行過程中所占空間的大小。5.高級問題初探: 算法分析與計算復雜性5.2 算法的計算時間有多長?49/55算法分析與計算復雜性算法復雜性分析示例主要關注點：循環(huán)的層數sum=0；（1次）for( i