第9章算法：程序與計(jì)算系統(tǒng)的靈魂第9章算法：程序與計(jì)算系統(tǒng)的靈魂一、算法的基本概念二、建立問(wèn)題的數(shù)學(xué)模型數(shù)學(xué)建模三、算法策略選擇算法思想四、算法設(shè)計(jì)算法思想的精確表達(dá)五、算法的實(shí)現(xiàn)--算法的程序設(shè)計(jì)六、算法的模擬與分析本章導(dǎo)圖符號(hào)化,計(jì)算化再語(yǔ)義化自然/社會(huì)問(wèn)題程序化執(zhí)行化算法的結(jié)果機(jī)器級(jí)程序--機(jī)器指令運(yùn)算器和控制器(CPU)-執(zhí)行算法自然/社會(huì)問(wèn)題的求解結(jié)果產(chǎn)生用0/1編碼：指令和數(shù)據(jù)存儲(chǔ)器：0/1存與取0/1化信號(hào)化存儲(chǔ)高級(jí)語(yǔ)言程序編譯執(zhí)行化匯編語(yǔ)言程序程序執(zhí)行匯編程序執(zhí)行“是否會(huì)編程序”，本質(zhì)上是“能否想出求解問(wèn)題的算法”，其次才是將算法用計(jì)算機(jī)可以識(shí)別的形式書(shū)寫(xiě)出來(lái)算法的重要性一、算法的基本概念理解算法類(lèi)問(wèn)題求解框架一、算法的基本概念算法計(jì)算機(jī)與軟件的靈魂?！八惴ā?Algorithm)一詞源于阿拉伯?dāng)?shù)學(xué)家阿科瓦里茨米(AlKhowarizmi)，其在公元825年寫(xiě)了著名的《波斯教科書(shū)》(PersianTextbook)，書(shū)中概括了進(jìn)行四則算術(shù)運(yùn)算的計(jì)算規(guī)則。算法是一個(gè)有窮規(guī)則的集合，它用規(guī)則規(guī)定了解決某一特定類(lèi)型問(wèn)題的運(yùn)算序列，或者規(guī)定了任務(wù)執(zhí)行或問(wèn)題求解的一系列步驟。如音樂(lè)樂(lè)譜、太極拳譜等都可看作廣義的算法什么是算法？一、算法的基本概念尋找兩個(gè)正整數(shù)的最大公約數(shù)的歐幾里德算法輸入：正整數(shù)M和正整數(shù)N輸出：M和N的最大公約數(shù)(設(shè)M>N)算法步驟：Step1.

M除以N,記余數(shù)為RStep2.如果R不是0，將N的值賦給M,R的值賦給N,返回Step1;否則,最大公約數(shù)是N,輸出N,算法結(jié)束。算法示例一、算法的基本概念有窮性：一個(gè)算法在執(zhí)行有窮步規(guī)則之后必須結(jié)束。確定性：算法的每一個(gè)步驟必須要確切地定義，不得有歧義性。輸入：算法有零個(gè)或多個(gè)的輸入。輸出：算法有一個(gè)或多個(gè)的輸出/結(jié)果，即與輸入有某個(gè)特定關(guān)系的量。能行性：算法中有待執(zhí)行的運(yùn)算和操作必須是相當(dāng)基本的(可以由機(jī)器自動(dòng)完成)，并能在有限時(shí)間內(nèi)完成?；具\(yùn)算：除法、賦值、邏輯判斷典型的“重復(fù)/循環(huán)”與“迭代”尋找兩個(gè)正整數(shù)的最大公約數(shù)的歐幾里德算法輸入：正整數(shù)M和正整數(shù)N輸出：M和N的最大公約數(shù)(設(shè)M>N)算法步驟：Step1.

M除以N,記余數(shù)為RStep2.如果R不是0，將N的值賦給M,R的值賦給N,返回Step1;否則,最大公約數(shù)是N,輸出N,算法結(jié)束。算法的五個(gè)特征一、算法的基本概念算法相關(guān)的知識(shí)算法算法策略數(shù)學(xué)建模數(shù)據(jù)結(jié)構(gòu)控制結(jié)構(gòu)程序設(shè)計(jì)算法正確性與復(fù)雜性問(wèn)題問(wèn)題的求解一、算法的基本概念第9章算法：程序與計(jì)算系統(tǒng)的靈魂一、算法的基本概念二、建立問(wèn)題的數(shù)學(xué)模型數(shù)學(xué)建模三、算法策略選擇算法思想四、算法設(shè)計(jì)算法思想的精確表達(dá)五、算法的實(shí)現(xiàn)--算法的程序設(shè)計(jì)六、算法的模擬與分析本章導(dǎo)圖數(shù)學(xué)建模是用數(shù)學(xué)語(yǔ)言描述實(shí)際現(xiàn)象的過(guò)程，即建立數(shù)學(xué)模型的過(guò)程。數(shù)學(xué)模型是對(duì)實(shí)際問(wèn)題的一種數(shù)學(xué)表述，是關(guān)于部分現(xiàn)實(shí)世界為某種目的的一個(gè)抽象的簡(jiǎn)化的數(shù)學(xué)結(jié)構(gòu)。二、建立問(wèn)題的數(shù)學(xué)模型數(shù)學(xué)建模算法類(lèi)問(wèn)題求解的第一步就是數(shù)學(xué)建?！臼纠扛缒崴贡て邩騿?wèn)題：“尋找走遍這7座橋且只許走過(guò)每座橋一次最后又回到原出發(fā)點(diǎn)的路徑”。這個(gè)算法是怎樣的呢?哥尼斯堡七橋問(wèn)題：抽象成一個(gè)“圖(Graph)”

,由節(jié)點(diǎn)和邊所構(gòu)成的一種結(jié)構(gòu)。由一個(gè)節(jié)點(diǎn)出發(fā)，又回到原出發(fā)節(jié)點(diǎn)，則連接該節(jié)點(diǎn)的邊數(shù)是否應(yīng)為偶數(shù)?這個(gè)問(wèn)題無(wú)解！無(wú)解的問(wèn)題還用構(gòu)造算法嗎?陸地--

節(jié)點(diǎn)連接陸地的橋梁--

連接節(jié)點(diǎn)的邊將社會(huì)/自然問(wèn)題轉(zhuǎn)化為數(shù)學(xué)問(wèn)題二、建立問(wèn)題的數(shù)學(xué)模型數(shù)學(xué)建模哥尼斯堡七橋問(wèn)題：“尋找走遍這7座橋且只許走過(guò)每座橋一次最后又回到原出發(fā)點(diǎn)的路徑”一般性問(wèn)題：“對(duì)給定的任意一個(gè)河道圖與任意多座橋判定可能不可能每座橋恰好走過(guò)一次?”。如能抽象成數(shù)學(xué)模型，則可將一個(gè)具體問(wèn)題的求解，推廣為一類(lèi)問(wèn)題的求解！數(shù)學(xué)模型，可描述一般性問(wèn)題二、建立問(wèn)題的數(shù)學(xué)模型數(shù)學(xué)建模“連通兩個(gè)節(jié)點(diǎn)間有路徑相連接”

“可達(dá)從一個(gè)節(jié)點(diǎn)出發(fā)能夠到達(dá)另一個(gè)節(jié)點(diǎn)”

“回路從一個(gè)節(jié)點(diǎn)出發(fā)最后又回到該節(jié)點(diǎn)的一條路徑”無(wú)向圖有向圖入度/出度節(jié)點(diǎn)的“度”“圖論”專(zhuān)門(mén)講這方面的內(nèi)容喲！經(jīng)過(guò)圖中每邊一次且僅一次的回路經(jīng)過(guò)圖中每節(jié)點(diǎn)一次且僅一次的回路歐拉回路-歐拉圖哈密爾頓回路-哈密爾頓圖偶度節(jié)點(diǎn)奇度節(jié)點(diǎn)數(shù)學(xué)模型，可發(fā)現(xiàn)不同類(lèi)別的問(wèn)題及其性質(zhì)二、建立問(wèn)題的數(shù)學(xué)模型數(shù)學(xué)建?！耙还P畫(huà)”凡是由偶度點(diǎn)組成的連通圖，一定可以一筆畫(huà)成。畫(huà)時(shí)可以把任一偶度點(diǎn)為起點(diǎn)，最后一定能以這個(gè)點(diǎn)為終點(diǎn)畫(huà)完此圖；凡是只有兩個(gè)奇度點(diǎn)的連通圖，其余都為偶度點(diǎn)，一定可以一筆畫(huà)成。畫(huà)時(shí)必須以一個(gè)奇度點(diǎn)為起點(diǎn)，另一個(gè)奇度點(diǎn)為終點(diǎn)。其余情況都不能一筆畫(huà)出。數(shù)學(xué)模型，可發(fā)現(xiàn)問(wèn)題求解的基本思路二、建立問(wèn)題的數(shù)學(xué)模型數(shù)學(xué)建模TSP問(wèn)題(TravelingSalesmanProblem，旅行商問(wèn)題)，威廉哈密爾頓爵士和英國(guó)數(shù)學(xué)家克克曼T.P.Kirkman于19世紀(jì)初提出TSP問(wèn)題．TSP問(wèn)題：有若干個(gè)城市，任何兩個(gè)城市之間的距離都是確定的，現(xiàn)要求一旅行商從某城市出發(fā)必須經(jīng)過(guò)每一個(gè)城市且只能在每個(gè)城市逗留一次，最后回到原出發(fā)城市，問(wèn)如何事先確定好一條最短的路線使其旅行的費(fèi)用最少。城市之間的距離什么是TSP問(wèn)題經(jīng)過(guò)圖中每節(jié)點(diǎn)一次且僅一次的回路哈密爾頓回路-哈密爾頓圖經(jīng)過(guò)圖中每節(jié)點(diǎn)一次且僅一次的回路；連接節(jié)點(diǎn)的邊有“權(quán)值”賦權(quán)-哈密爾頓圖二、建立問(wèn)題的數(shù)學(xué)模型數(shù)學(xué)建模TSP是最有代表性的組合優(yōu)化問(wèn)題之一，在半導(dǎo)體制造(線路規(guī)劃)、物流運(yùn)輸(路徑規(guī)劃)等行業(yè)有著廣泛的應(yīng)用?，F(xiàn)實(shí)中的很多問(wèn)題都是TSP問(wèn)題二、建立問(wèn)題的數(shù)學(xué)模型數(shù)學(xué)建模

將TSP問(wèn)題抽象為數(shù)學(xué)問(wèn)題

進(jìn)一步簡(jiǎn)化蠻干/遍歷二、建立問(wèn)題的數(shù)學(xué)模型數(shù)學(xué)建模通過(guò)自然數(shù)及其下標(biāo)將不同類(lèi)型的數(shù)據(jù)關(guān)聯(lián)起來(lái)，是算法類(lèi)問(wèn)題抽象的重要方法。表達(dá)四個(gè)核心要素：輸入輸出約束目標(biāo)現(xiàn)實(shí)問(wèn)題抽象后是否是相同的問(wèn)題？二、建立問(wèn)題的數(shù)學(xué)模型數(shù)學(xué)建模第9章算法：程序與計(jì)算系統(tǒng)的靈魂一、算法的基本概念二、建立問(wèn)題的數(shù)學(xué)模型數(shù)學(xué)建模三、算法策略選擇算法思想四、算法設(shè)計(jì)算法思想的精確表達(dá)五、算法的實(shí)現(xiàn)--算法的程序設(shè)計(jì)六、算法的模擬與分析本章導(dǎo)圖所有路徑組合及其長(zhǎng)度城市之間的距離三、算法策略選擇算法思想蠻干/遍歷是基本的算法策略遍歷算法求解TSP問(wèn)題：列出每一條可供選擇的路線，計(jì)算出每條路線的總里程，最后從中選出一條最短的路線。組合爆炸路徑組合數(shù)目：(n-1)!20個(gè)城市，遍歷總數(shù)1.216×1017計(jì)算機(jī)以每秒檢索1000萬(wàn)條路線的計(jì)算速度，需386年。所有路徑組合及其長(zhǎng)度城市之間的距離蠻干/遍歷策略會(huì)帶來(lái)怎樣的問(wèn)題？三、算法策略選擇算法思想TSP問(wèn)題的難解性：隨著城市數(shù)量n的上升，TSP問(wèn)題的遍歷計(jì)算量(n-1)！劇增，計(jì)算資源將難以承受。2001年解決了德國(guó)15112個(gè)城市的TSP問(wèn)題，使用了美國(guó)Rice大學(xué)和普林斯頓大學(xué)之間互連的、速度為500MHz

的CompaqEV6Alpha處理器組成的110臺(tái)計(jì)算機(jī)，所有計(jì)算機(jī)花費(fèi)的時(shí)間之和為22.6年。AnoptimalTSPtourthroughGermany’s15largestcities.Itistheshortestamong43589145600possibletoursvisitingeachcityexactlyonce.問(wèn)題的難解性三、算法策略選擇算法思想TSP問(wèn)題，有沒(méi)有其他求解算法呢？最優(yōu)解

vs.可行解不同的算法設(shè)計(jì)策略：遍歷、搜索算法分治算法貪心算法動(dòng)態(tài)規(guī)劃算法……可行解最優(yōu)解TSP問(wèn)題的可行解與最優(yōu)解示意算法策略尋找其他策略降低計(jì)算量三、算法策略選擇算法思想貪心算法是一種算法策略?；舅枷搿敖癯芯平癯怼?一定要做當(dāng)前情況下的最好選擇，否則將來(lái)可能會(huì)后悔，故名“貪心”。從某一個(gè)城市開(kāi)始，每次選擇一個(gè)城市，直到所有城市都被走完。每次在選擇下一個(gè)城市的時(shí)候，只考慮當(dāng)前情況，保證迄今為止經(jīng)過(guò)的路徑總距離最短。城市之間的距離另一種策略：貪心算法三、算法策略選擇算法思想第9章算法：程序與計(jì)算系統(tǒng)的靈魂一、算法的基本概念二、建立問(wèn)題的數(shù)學(xué)模型數(shù)學(xué)建模三、算法策略選擇算法思想四、算法設(shè)計(jì)算法思想的精確表達(dá)五、算法的實(shí)現(xiàn)--算法的程序設(shè)計(jì)六、算法的模擬與分析本章導(dǎo)圖城市映射為編號(hào):A1,B2,C3,D4城市間距離關(guān)系:表或二維數(shù)組D，用D[i][j]或D[i,j]來(lái)確定欲處理的每一個(gè)元素訪問(wèn)路徑/解:一維數(shù)組S，用S[j]來(lái)確定每一個(gè)元素1432{A->D->C->B->A}SS[1]S[2]S[3]S[4]DD[2][3]四、算法設(shè)計(jì)算法思想的精確表達(dá)問(wèn)題求解相關(guān)數(shù)據(jù)如何存儲(chǔ)？數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其操作的總稱(chēng)，它提供了問(wèn)題求解/算法的數(shù)據(jù)操縱機(jī)制。(數(shù)據(jù)的)邏輯結(jié)構(gòu)(數(shù)據(jù)的)存儲(chǔ)結(jié)構(gòu)操作反映邏輯語(yǔ)義關(guān)系為便于計(jì)算系統(tǒng)處理為什么需要數(shù)據(jù)結(jié)構(gòu)四、算法設(shè)計(jì)算法思想的精確表達(dá)*p變量、指針變量與存儲(chǔ)單元四、算法設(shè)計(jì)算法思想的精確表達(dá)“樹(shù)”的存儲(chǔ)結(jié)構(gòu):一個(gè)存儲(chǔ)單元存儲(chǔ)“數(shù)據(jù)元素”

；一個(gè)存儲(chǔ)單元存儲(chǔ)“指針”，指示數(shù)據(jù)元素之間的邏輯關(guān)系150120160數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)503070100數(shù)據(jù)元素對(duì)應(yīng)數(shù)據(jù)元素的指針—指向該元素的父元素典型的數(shù)據(jù)結(jié)構(gòu)--“樹(shù)”：一種存儲(chǔ)方法四、算法設(shè)計(jì)算法思想的精確表達(dá)150120160503070100數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)中，通過(guò)指針的變化,不改變數(shù)據(jù)元素的存儲(chǔ),但卻改變了數(shù)據(jù)元素之間的邏輯關(guān)系120典型的數(shù)據(jù)結(jié)構(gòu)--“樹(shù)”：一種存儲(chǔ)方法四、算法設(shè)計(jì)算法思想的精確表達(dá)150120160503070100數(shù)據(jù)元素對(duì)應(yīng)數(shù)據(jù)元素的左指針—指向該元素的左側(cè)子結(jié)點(diǎn)對(duì)應(yīng)數(shù)據(jù)元素的右指針—指向該元素的右側(cè)子結(jié)點(diǎn)“樹(shù)”的另一種存儲(chǔ)結(jié)構(gòu),用兩個(gè)指針表達(dá)數(shù)據(jù)之間的邏輯關(guān)系，一個(gè)指向其左數(shù)據(jù)元素，一個(gè)指向其右數(shù)據(jù)元素。數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)不同，數(shù)據(jù)之間的操作方法也是不同的典型的數(shù)據(jù)結(jié)構(gòu)--“樹(shù)”：另一種存儲(chǔ)方法四、算法設(shè)計(jì)算法思想的精確表達(dá)150120160503070100數(shù)據(jù)的邏輯結(jié)構(gòu)150120160503070100數(shù)據(jù)的邏輯結(jié)構(gòu)110Null動(dòng)手練習(xí)一下練習(xí)一下…四、算法設(shè)計(jì)算法思想的精確表達(dá)順序結(jié)構(gòu)：“執(zhí)行A，然后執(zhí)行B”，是按順序執(zhí)行一條條規(guī)則的一種結(jié)構(gòu)。分支結(jié)構(gòu)：“如果Q成立，那么執(zhí)行A，否則執(zhí)行B”

，Q是某些邏輯條件，即按條件判斷結(jié)果決定執(zhí)行哪些規(guī)則的一種結(jié)構(gòu)。循環(huán)結(jié)構(gòu)：控制指令或規(guī)則的多次執(zhí)行的一種結(jié)構(gòu)迭代(iteration)循環(huán)結(jié)構(gòu)又分為有界循環(huán)結(jié)構(gòu)和條件循環(huán)結(jié)構(gòu)。有界循環(huán)：“執(zhí)行A指令N次”，其中N是一個(gè)整數(shù)。條件循環(huán)：某些時(shí)候稱(chēng)為無(wú)界循環(huán)，“重復(fù)執(zhí)行A直到條件Q成立”或“當(dāng)Q成立時(shí)反復(fù)執(zhí)行A”，其中Q是條件。算法與程序的基本控制結(jié)構(gòu)算法的類(lèi)自然語(yǔ)言表達(dá)方法四、算法設(shè)計(jì)算法思想的精確表達(dá)Startofthealgorithm(算法開(kāi)始)(1)輸入N的值；(2)設(shè)i的值為1；sum的值為0；(3)如果i<=N，則執(zhí)行第(4)步，否則轉(zhuǎn)到第(7)步執(zhí)行；(4)計(jì)算sum+i，并將結(jié)果賦給sum；(5)計(jì)算i+1，并將結(jié)果賦給i;(6)返回到第3步繼續(xù)執(zhí)行；(7)輸出sum的結(jié)果。Endofthealgorithm(算法結(jié)束)

自然語(yǔ)言表示的算法容易出現(xiàn)二義性、不確定性等問(wèn)題示例【示例】sum=1+2+3+4+…+n求和問(wèn)題的算法描述四、算法設(shè)計(jì)算法思想的精確表達(dá)流程圖的基本表示符號(hào)

矩形框：表示一組順序執(zhí)行的規(guī)則或者程序語(yǔ)句。菱形框：表示條件判斷，并根據(jù)判斷結(jié)果執(zhí)行不同的分支。圓形框：表示算法或程序的開(kāi)始或結(jié)束。箭頭線：表示算法或程序的走向。算法的程序流程圖表達(dá)方法四、算法設(shè)計(jì)算法思想的精確表達(dá)三種控制結(jié)構(gòu)的流程圖表達(dá)開(kāi)始第1條規(guī)則或語(yǔ)句第n條規(guī)則或語(yǔ)句結(jié)束順序結(jié)構(gòu)的流程圖開(kāi)始條件成立否？是否條件成立時(shí)執(zhí)行的規(guī)則或語(yǔ)句結(jié)束條件不成立時(shí)執(zhí)行的規(guī)則或語(yǔ)句分支結(jié)構(gòu)的流程圖循環(huán)結(jié)構(gòu)的流程圖初始化部分開(kāi)始循環(huán)控制條件成立？修改部分需循環(huán)執(zhí)行的規(guī)則或語(yǔ)句。即：循環(huán)體結(jié)束是否循環(huán)結(jié)束算法的程序流程圖表達(dá)方法四、算法設(shè)計(jì)算法思想的精確表達(dá)循環(huán)結(jié)構(gòu)的兩種情況的流程圖表達(dá)初始化部分開(kāi)始循環(huán)控制條件成立？修改部分需循環(huán)執(zhí)行的規(guī)則或語(yǔ)句結(jié)束是否循環(huán)結(jié)束有界循環(huán)結(jié)構(gòu)的流程圖(循環(huán)次數(shù)確定)初始化部分開(kāi)始循環(huán)控制條件成立？修改部分需循環(huán)執(zhí)行的規(guī)則或語(yǔ)句結(jié)束否循環(huán)未結(jié)束是條件循環(huán)結(jié)構(gòu)的流程圖(循環(huán)次數(shù)不確定)算法的程序流程圖表達(dá)方法四、算法設(shè)計(jì)算法思想的精確表達(dá)【示例】歐幾里德算法流程圖示例四、算法設(shè)計(jì)算法思想的精確表達(dá)求解TSP問(wèn)題的遍歷算法的表達(dá)當(dāng)前最短路徑MS設(shè)為空，當(dāng)前最短距離DTemp設(shè)為最大值開(kāi)始所有路徑組合完畢否？結(jié)束否是組合一條新路徑S并計(jì)算該路徑的距離Distance比當(dāng)前最短距離小嗎？將該路徑記錄為當(dāng)前最短路徑，并用其距離值更新當(dāng)前最短距離輸出當(dāng)前最短路徑及當(dāng)前最短距離是否將思想/策略轉(zhuǎn)變?yōu)椤安襟E”1234SS[1]S[2]S[3]S[4]124313241342Distance=D[S[4]][S[1]]+

D[S[i]][S[i+1]]i=1to3D當(dāng)前最短路徑1234MS當(dāng)前最短距離DTemp四、算法設(shè)計(jì)算法思想的精確表達(dá)求解TSP問(wèn)題的貪心算法的表達(dá)依次訪問(wèn)過(guò)的城市編號(hào)被記錄在S[1],S[2],…,S[N}中,即第I次訪問(wèn)的城市記錄在S[I]中。Step(1)：從1號(hào)城市開(kāi)始訪問(wèn)，將城市編號(hào)1賦值給S[1]。Step(6)：第I次訪問(wèn)的城市為城市j，其距第I-1次訪問(wèn)的城市的距離最短。StartoftheAlgorithm(1)S[1]=1;(2)Sum=0;(3)初始化距離數(shù)組D[N,N];(4)I=2;(5)從所有未訪問(wèn)過(guò)的城市中查找距離S[I-1]最近的城市j;(6)S[I]=j;(7)I=I+1;(8)Sum=Sum+Dtemp;(9)如果I<=N，轉(zhuǎn)步驟(5)，否則，轉(zhuǎn)步驟(10);(10)Sum=Sum+D[1,j]；(11)逐個(gè)輸出S[N]中的全部元素;(12)輸出Sum。EndoftheAlgorithmD1

SS[1]S[2]S[3]S[4]I=2,3,4當(dāng)前要找第幾個(gè)j=1,

2,3,4城市號(hào)四、算法設(shè)計(jì)算法思想的精確表達(dá)求解TSP問(wèn)題的貪心算法的表達(dá)前述第5步“從所有未訪問(wèn)過(guò)的城市中查找距離S[I-1]最近的城市j”還是不夠明確，需要進(jìn)一步細(xì)化(5.1)K=2;(5.2)將Dtemp設(shè)為一個(gè)大數(shù)(比所有兩個(gè)城市之間的距離都大)

(5.3)L=1；

(5.4)如果S[L]==K，轉(zhuǎn)步驟5.8；//該城市已出現(xiàn)過(guò)，跳過(guò)

(5.5)L=L+1；

(5.6)如果L<I，轉(zhuǎn)5.4；(5.7)如果D[K,S[I-1]]<Dtemp,則j=K;Dtemp＝D[K,S[I-1]]；(5.8)K=K+1;(5.9)如果K<=N，轉(zhuǎn)步驟5.3。1

SS[1]S[2]S[3]S[4]K=2,3,4城市號(hào)L=1,

2,…,I-1從第1個(gè)訪問(wèn)過(guò)的，到第I-1個(gè)訪問(wèn)過(guò)的I=2,3,4當(dāng)前要找第幾個(gè)四、算法設(shè)計(jì)算法思想的精確表達(dá)求解TSP問(wèn)題的貪心算法的表達(dá)1

SS[1]S[2]S[3]S[4]K=2,3,4城市號(hào)L=1,

2,…,I-1從第1個(gè)訪問(wèn)過(guò)的，到第I-1個(gè)訪問(wèn)過(guò)的I=2,3,4當(dāng)前要找第幾個(gè)四、算法設(shè)計(jì)算法思想的精確表達(dá)閱讀并理解算法的能力計(jì)算學(xué)科的學(xué)生不僅能夠設(shè)計(jì)算法，而且會(huì)描述和表達(dá)算法，更要能讀懂算法。外層循環(huán)，I從2至N循環(huán)；I-1個(gè)城市已訪問(wèn)過(guò)，正在找與第I-1個(gè)城市最近距離的城市；已訪問(wèn)過(guò)的城市號(hào)存儲(chǔ)在S[]中。中層循環(huán),K從2號(hào)城市至N號(hào)城市循環(huán),判斷D[K,S[I-1]]是否是最小值，j記錄了最小距離的城市號(hào)K。內(nèi)層循環(huán)，L從1至I-1,循環(huán)判斷第K號(hào)城市是否是已訪問(wèn)過(guò)的城市，如是則不參加最小距離的比較；四、算法設(shè)計(jì)算法思想的精確表達(dá)第9章算法：程序與計(jì)算系統(tǒng)的靈魂一、算法的基本概念二、建立問(wèn)題的數(shù)學(xué)模型數(shù)學(xué)建模三、算法策略選擇算法思想四、算法設(shè)計(jì)算法思想的精確表達(dá)五、算法的實(shí)現(xiàn)--算法的程序設(shè)計(jì)六、算法的模擬與分析本章導(dǎo)圖程序設(shè)計(jì)過(guò)程：編輯源程序

編譯

鏈接

執(zhí)行。一套書(shū)寫(xiě)程序的語(yǔ)法規(guī)則計(jì)算機(jī)語(yǔ)言程序設(shè)計(jì)環(huán)境：編輯、編譯、連接、調(diào)試、運(yùn)行一體化平臺(tái)高級(jí)語(yǔ)言程序目標(biāo)程序可執(zhí)行程序編輯程序編譯程序連接程序公用函數(shù)庫(kù)調(diào)試程序五、算法的實(shí)現(xiàn)--算法的程序設(shè)計(jì)算法的實(shí)現(xiàn)環(huán)境與過(guò)程SS[0]S[1]S[2]S[3]K從1,…,n-1是城市的編號(hào)I是至今已訪問(wèn)過(guò)的城市數(shù)S[0]至S[I-1]中存儲(chǔ)的是已訪問(wèn)過(guò)的城市的編號(hào)main(){…//前面已為K和I賦過(guò)值L=0;

Found=0;do{

if(S[L]==K) {

Found=1;

break;

} elseL=L+1;}while(L<I); //L從1到I循環(huán)ifFound==0{//城市K未出現(xiàn)過(guò)

}else{//城市K出現(xiàn)過(guò)}...}判斷城市K是否是已訪問(wèn)過(guò)的城市1432實(shí)現(xiàn)算法的程序：閱讀與理解五、算法的實(shí)現(xiàn)--算法的程序設(shè)計(jì)SS[0]S[1]S[2]S[3]K從1,…,n-1是城市的編號(hào)I是至今已訪問(wèn)過(guò)的城市數(shù)S[I-1]中存儲(chǔ)的是當(dāng)前訪問(wèn)過(guò)的城市編號(hào)，要找第I個(gè)程序main(){…

K=1;

Dtemp=10000;

do{//K從1到n-1循環(huán)

L=0;

Found=0; do{

if(S[L]==K) {

Found=1;

break;

} elseL=L+1; }while(L<I); //L從1到I循環(huán)

if(Found==0

&&D[K][S[I-1]]<Dtemp){

j=K;

Dtemp=D[K][S[I-1]];

} K=K+1;}while(K<n);

//K從1到n-1循環(huán)

S[I]=j;Sum=Sum+Dtemp;…}尋找下一個(gè)未訪問(wèn)過(guò)的城市j,且其距當(dāng)前訪問(wèn)城市S[I-1]距離最短1432D[K][S[I-1]]為城市K距當(dāng)前訪問(wèn)過(guò)的城市的距離實(shí)現(xiàn)算法的程序：閱讀與理解五、算法的實(shí)現(xiàn)--算法的程序設(shè)計(jì)實(shí)現(xiàn)算法的程序：閱讀與理解TSP問(wèn)題的貪心算法程序?qū)嵗?、算法的?shí)現(xiàn)--算法的程序設(shè)計(jì)第9章算法：程序與計(jì)算系統(tǒng)的靈魂一、算法的基本概念二、建立問(wèn)題的數(shù)學(xué)模型數(shù)學(xué)建模三、算法策略選擇算法思想四、算法設(shè)計(jì)算法思想的精確表達(dá)五、算法的實(shí)現(xiàn)--算法的程序設(shè)計(jì)六、算法的模擬與分析本章導(dǎo)圖算法的正確性問(wèn)題問(wèn)題求解的過(guò)程、方法——算法是正確的嗎？算法的輸出是問(wèn)題的解嗎？滿足問(wèn)題求解約束的解就是問(wèn)題的解，但不一定是最優(yōu)解。20世紀(jì)60年代，美國(guó)一架發(fā)往金星的航天飛機(jī)由于控制程序出錯(cuò)而永久丟失在太空中。算法的效果評(píng)價(jià)算法的輸出是最優(yōu)解還是可行解？如果是可行解，與最優(yōu)解的偏差多大？?jī)煞N評(píng)價(jià)方法：證明方法：利用數(shù)學(xué)方法證明；仿真分析方法：產(chǎn)生或選取大量的、具有代表性的問(wèn)題實(shí)例，利用該算法對(duì)這些問(wèn)題實(shí)例進(jìn)行求解，并對(duì)算法產(chǎn)生的結(jié)果進(jìn)行統(tǒng)計(jì)分析。算法獲得的解是最優(yōu)的嗎?六、算法的模擬與分析算法的模擬與分析算法是正確的嗎?TSP問(wèn)題貪心算法的正確性評(píng)價(jià)直觀上只需檢查算法的輸出結(jié)果中，每個(gè)城市出現(xiàn)且僅出現(xiàn)一次，該結(jié)果即是TSP問(wèn)題的可行解，說(shuō)明算法正確地求解了這些問(wèn)題實(shí)例1234SS[1]S[2]S[3]S[4]六、算法的模擬與分析TSP問(wèn)題貪心算法的效果評(píng)價(jià)如果實(shí)例的最優(yōu)解已知（問(wèn)題規(guī)模小或問(wèn)題已被成功求解），利用統(tǒng)計(jì)方法對(duì)若干問(wèn)題實(shí)例的算法結(jié)果與最優(yōu)解進(jìn)行對(duì)比分析，即可對(duì)其進(jìn)行效果評(píng)價(jià)；對(duì)于較大規(guī)模的問(wèn)題實(shí)例，其最優(yōu)解往往是未知的，因此，算法的效果評(píng)價(jià)只能借助于與前人算法結(jié)果的比較。1234SS[1]S[2]S[3]S[4]六、算法的模擬與分析時(shí)間復(fù)雜性:如果一個(gè)問(wèn)題的規(guī)模是n，解這一問(wèn)題的某一算法所需要的時(shí)間為T(mén)(n)，它是n的某一函數(shù)，則T(n)稱(chēng)為這一算法的“時(shí)間復(fù)雜性”。“大O記法”：基本參數(shù)n——問(wèn)題實(shí)例的規(guī)模把復(fù)雜性或運(yùn)行時(shí)間表達(dá)為n的函數(shù)。“O”表示量級(jí)(order)，允許使用“=”代替“≈”，如n2+n+1=Ο(n2)?？臻g復(fù)雜性：算法在執(zhí)行過(guò)程中所占存儲(chǔ)空間的大小。算法獲得結(jié)果的時(shí)間有多長(zhǎng)?算法復(fù)雜性O(shè)(f(n))算法的時(shí)間復(fù)雜度與空間復(fù)雜度六、算法的模擬與分析sum=0；

（1次）for(i=1;i<=n;i++)

（n次）{for(j=1;j<=n;j++)（n2次）

{sum++；}

（n2次）}解：T(n)=2n2+n+1=O(n2)主要關(guān)注點(diǎn)：循環(huán)的層數(shù)算法復(fù)雜性分析示例六、算法的模擬與分析TSP問(wèn)題貪心算法的復(fù)雜性分析nn2n3一個(gè)關(guān)于n的三重循環(huán)。時(shí)間復(fù)雜度是O(n3)。六、算法的模擬與分析TSP問(wèn)題遍歷算法的復(fù)雜性分析列出每一條可供選擇的路線，計(jì)算出每條路線的總里程，最后從中選出一條最短的路線。路徑組合數(shù)目為(n-1)!時(shí)間復(fù)雜度是O((n-1)!)當(dāng)前最短路徑設(shè)為空，當(dāng)前最短距離設(shè)為最大值開(kāi)始所有路徑組合完畢否？結(jié)束否是組合一條新路徑并計(jì)算該路徑的距離比當(dāng)前最短距離小嗎？將該路徑記錄為當(dāng)前最短路徑，并用其距離值更新當(dāng)前最短距離輸出當(dāng)前最短路徑及當(dāng)前最短距離是否六、算法的模擬與分析問(wèn)題規(guī)模n計(jì)算量1010！2020！100100！10001000！1000010000！20！=1.216×1017203=

8000O(n3)O(3n)0.2秒4

1028秒=1015年注：每秒百萬(wàn)次，n=60，1015年相當(dāng)于10億臺(tái)計(jì)算機(jī)計(jì)算一百萬(wàn)年O(n3)與O(3n)的差別，O(n!)與O(n3)的差別O(bn),O(n!)O(1),O(logn),O(n),O(nlogn),O(nb)不同的算法復(fù)雜性量級(jí)六、算法的模擬與分析O(1),O(logn),O(n),O(nlogn),O(nb)O(bn),O(n!)當(dāng)算法的復(fù)雜度是一個(gè)多項(xiàng)式，如O(n2)時(shí)，則對(duì)于大規(guī)模問(wèn)題，該算法是可以在有限時(shí)間內(nèi)被計(jì)算機(jī)完成的。例如，TSP問(wèn)題的貪心算法

O(n3)

。當(dāng)算法的復(fù)雜度是用指數(shù)函數(shù)表示如O(2n)或階乘函數(shù)表示如O(n!)，則當(dāng)n很大（如10000）時(shí)，該算法是計(jì)算機(jī)在有限時(shí)間內(nèi)無(wú)法處理的。例如TSP問(wèn)題的遍歷算法O((n-1)!)。有限時(shí)間內(nèi)是否能完成算法的執(zhí)行？六、算法的模擬與分析算法復(fù)雜性：求解問(wèn)題的某一個(gè)算法的復(fù)雜性。計(jì)算復(fù)雜性：能求問(wèn)題精確解的那個(gè)算法的復(fù)雜性。計(jì)算復(fù)雜性與算法復(fù)雜性計(jì)算復(fù)雜性是指問(wèn)題的一種特性，即利用計(jì)算機(jī)求解問(wèn)題的難易性或難易程度問(wèn)題的計(jì)算復(fù)雜性計(jì)算機(jī)在有限時(shí)間內(nèi)能夠求解的--【可求解問(wèn)題】計(jì)算機(jī)在有限時(shí)間內(nèi)不能求解的--【難求解問(wèn)題】計(jì)算機(jī)完全不能求解的--【不可計(jì)算問(wèn)題】六、算法的模擬與分析對(duì)解空間中的每一個(gè)可能解進(jìn)行驗(yàn)證，直到所有的解都被驗(yàn)證是否正確，便能得到精確的結(jié)果精確解可能是O(n!)或O(an)近似解求解算法近似解應(yīng)該是O(na)?=|近似解–

精確解|滿意解：?充分小時(shí)的近似解TSP問(wèn)題的遍歷算法(又稱(chēng)窮舉或蠻干)TSP問(wèn)題的貪心算法TSP問(wèn)題的計(jì)算復(fù)雜性與算法復(fù)雜性TSP問(wèn)題的計(jì)算復(fù)雜度：

O((n-1)!)TSP問(wèn)題的遍歷算法的時(shí)間復(fù)雜度：O((n-1)!)TSP問(wèn)題的貪心算法的時(shí)間復(fù)雜度：O(n3)。算法復(fù)雜性-某一個(gè)算法的復(fù)雜性計(jì)算復(fù)雜性-求精確解的那個(gè)算法的復(fù)雜性六、算法的模擬與分析P類(lèi)問(wèn)題：多項(xiàng)式問(wèn)題(PolynomialProblem)，指計(jì)算機(jī)可以在有限時(shí)間內(nèi)求解的問(wèn)題，即：可以找出一個(gè)呈現(xiàn)O(na)復(fù)雜性算法的問(wèn)題，其中a為常數(shù)。NP類(lèi)問(wèn)題：非確定性多項(xiàng)式問(wèn)題(Non-deterministicPolynomial)。有些問(wèn)題，其答案是無(wú)法直接計(jì)算得到的，只能通過(guò)間接的猜算或試算來(lái)得到結(jié)果，這就是非確定性問(wèn)題(Non-deterministic)。雖然在多項(xiàng)式時(shí)間內(nèi)難于求解但不難判斷給定一個(gè)解的正確性的問(wèn)題，即：在多項(xiàng)式時(shí)間內(nèi)可以由一個(gè)算法驗(yàn)證一個(gè)解是否正確的非確定性問(wèn)題，就是NP類(lèi)問(wèn)題。NPC問(wèn)題：如果NP問(wèn)題的所有可能答案都可以在多項(xiàng)式時(shí)間內(nèi)進(jìn)行正確與否的驗(yàn)算的話就叫做完全非確定性多項(xiàng)式問(wèn)題(NP-Complete)。問(wèn)：加密算法應(yīng)設(shè)計(jì)成一個(gè)什么問(wèn)題呢？P類(lèi)問(wèn)題NP類(lèi)問(wèn)題NPC類(lèi)問(wèn)題難解性問(wèn)題NP-HardNP難問(wèn)題可解性問(wèn)題與難解性問(wèn)題六、算法的模擬與分析問(wèn)題復(fù)雜性難解性問(wèn)題可解性問(wèn)題與難解性問(wèn)題所有可以在多項(xiàng)式時(shí)間內(nèi)求解的問(wèn)題，稱(chēng)為【P類(lèi)問(wèn)題】所有在多項(xiàng)式時(shí)間內(nèi)可以驗(yàn)證的問(wèn)題，稱(chēng)為【NP類(lèi)問(wèn)題】，P?NP。Openproblem:P=NP?美國(guó)克雷數(shù)學(xué)研究所百萬(wàn)大獎(jiǎng)難題。六、算法的模擬與分析第10章受限資源約束下的算法—排序問(wèn)題求解示例第10章受限資源約束下的算法—排序問(wèn)題求解示例一、為什么要研究排序問(wèn)題待求解問(wèn)題的理解二、基本排序算法三、PageRank排序--排序問(wèn)題的不同思考方法本章導(dǎo)圖一、為什么要研究排序問(wèn)題待求解問(wèn)題的理解對(duì)一組對(duì)象按照某種規(guī)則進(jìn)行有序排列。通常是把一組對(duì)象整理成按關(guān)鍵字遞增(或遞減)的排列，關(guān)鍵字是指對(duì)象的一個(gè)用于排序的特性。例如：對(duì)一組“人”，按“年齡”或“身高”排序；

對(duì)一組“商品”，按“價(jià)格”排序；

對(duì)一組“網(wǎng)頁(yè)”，按“重要度”排序；

對(duì)一組“詞匯”，按“首字母”字典序排序?！?/p>

…為什么要研究排序算法--結(jié)構(gòu)化數(shù)據(jù)表查找問(wèn)題(2)為什么要研究排序問(wèn)題?結(jié)構(gòu)化數(shù)據(jù)表的查找問(wèn)題【算法A：未排序數(shù)據(jù)查找算法】StartofalgorithmStep1.從數(shù)據(jù)表的第1條記錄開(kāi)始，直到其最后一條記錄為止，讀取每一條記錄，做Step2。Step2.對(duì)每一條記錄，判斷成績(jī)是否等于給定的分?jǐn)?shù)：如果是，則輸出；如果不是，則不輸出。Endofalgorithm學(xué)號(hào)姓名成績(jī)120300101李鵬88120300105張偉66120300107閆寧95120300102王剛79120300103李寧94120300106徐月85120300108杜巖44120300104趙凱69120300109江海77120300110周峰73查找成績(jī)?yōu)?0分的所有同學(xué)?算法效率：讀取并處理所有記錄，即n條記錄數(shù)據(jù)表記錄數(shù):n未排序一、為什么要研究排序問(wèn)題待求解問(wèn)題的理解為什么要研究排序算法--結(jié)構(gòu)化數(shù)據(jù)表查找問(wèn)題(2)為什么要研究排序問(wèn)題?結(jié)構(gòu)化數(shù)據(jù)表的查找與統(tǒng)計(jì)需要排序【算法B：已排序數(shù)據(jù)查找算法】StartofalgorithmStep1.從數(shù)據(jù)表的第1條記錄開(kāi)始，直到其最后一條記錄為止，讀取每一條記錄，做Step2和Step3步。Step2.對(duì)每一條記錄，判斷成績(jī)是否等于給定的分?jǐn)?shù)：如果等于，則輸出；如果不等于，則不輸出。Step3.判斷該條記錄的成績(jī)是否小于給定的分?jǐn)?shù)：如果不是，則繼續(xù)；否則，退出循環(huán)，算法結(jié)束。Endofalgorithm學(xué)號(hào)姓名成績(jī)120300107閆寧95120300103李寧94120300101李鵬88120300106徐月85120300102王剛79120300109江海77120300110周峰73120300104趙凱69120300105張偉66120300108杜巖44查找成績(jī)?yōu)?0分的所有同學(xué)?算法效率：讀取并處理部分記錄，即<=n條記錄數(shù)據(jù)表記錄數(shù):n已排序一、為什么要研究排序問(wèn)題待求解問(wèn)題的理解結(jié)構(gòu)化數(shù)據(jù)表的查找與統(tǒng)計(jì)需要排序?qū)W號(hào)姓名成績(jī)120300107閆寧95120300103李寧94120300101李鵬88120300106徐月85120300102王剛79120300109江海77120300110周峰73120300104趙凱69120300105張偉66120300108杜巖44查找成績(jī)?yōu)?0分的所有同學(xué)?數(shù)據(jù)表記錄數(shù):n【算法C：已排序數(shù)據(jù)查找算法】StartofalgorithmStep1.假設(shè)數(shù)據(jù)表的最大記錄數(shù)是n，待查詢區(qū)間的起始記錄位置Start為1，終止記錄位置Finish為n；Step2.計(jì)算中間記錄位置I=(Start+Finish)/2，讀取第I條記錄。Step3.判斷第I條記錄成績(jī)是否大于給定查找分?jǐn)?shù)：(1)如果是小于，調(diào)整Finish=I-1,如果Start>Finish則結(jié)束，否則繼續(xù)做Step2；(2)如果是大于，調(diào)整Start=I+1，如果Start>Finish則結(jié)束，否則繼續(xù)做Step2；(3)如果是等于，則輸出，繼續(xù)讀取I周?chē)械某煽?jī)與給定查找條件相等的記錄并輸出，直到所有相等記錄查詢輸出完畢則算法結(jié)束。Endofalgorithm算法效率：除極端情況外讀取并處理<=n/2條記錄已排序一、為什么要研究排序問(wèn)題待求解問(wèn)題的理解為什么要研究排序算法--結(jié)構(gòu)化數(shù)據(jù)表查找問(wèn)題(2)為什么要研究排序問(wèn)題?結(jié)構(gòu)化數(shù)據(jù)表的查找與統(tǒng)計(jì)需要排序?qū)W號(hào)姓名成績(jī)120300107閆寧95120300103李寧94120300101李鵬88120300106徐月85120300102王剛79120300109江海77120300110周峰73120300104趙凱69120300105張偉66120300108杜巖44學(xué)號(hào)姓名成績(jī)120300101李鵬88120300105張偉66120300107閆寧95120300102王剛79120300103李寧94120300106徐月85120300108杜巖44120300104趙凱69120300109江海77120300110周峰73統(tǒng)計(jì)各個(gè)分?jǐn)?shù)段的人數(shù)統(tǒng)計(jì)每個(gè)同學(xué)的平均分?jǐn)?shù)統(tǒng)計(jì)每門(mén)課的平均分?jǐn)?shù)???算法效率：需要讀取并處理???條記錄才能完成呢？一、為什么要研究排序問(wèn)題待求解問(wèn)題的理解結(jié)構(gòu)化數(shù)據(jù)表的查找與統(tǒng)計(jì)需要排序?qū)W號(hào)姓名成績(jī)120300107閆寧95120300103李寧94120300101李鵬88120300106徐月85120300102王剛79120300109江海77120300110周峰73120300104趙凱69120300105張偉66120300108杜巖44學(xué)號(hào)姓名成績(jī)120300101李鵬88120300105張偉66120300107閆寧95120300102王剛79120300103李寧94120300106徐月85120300108杜巖44120300104趙凱69120300109江海77120300110周峰73統(tǒng)計(jì)各個(gè)分?jǐn)?shù)段的人數(shù)統(tǒng)計(jì)每個(gè)同學(xué)的平均分?jǐn)?shù)統(tǒng)計(jì)每門(mén)課的平均分?jǐn)?shù)???算法效率：需要讀取并處理???條記錄才能完成呢？排序算法是計(jì)算學(xué)科中很重要的算法排序算法是很多復(fù)雜算法的基礎(chǔ)當(dāng)對(duì)數(shù)據(jù)集合需要多遍處理時(shí)，先排序-好一、為什么要研究排序問(wèn)題待求解問(wèn)題的理解為什么要研究排序算法非結(jié)構(gòu)化的數(shù)據(jù)文檔查找問(wèn)題(1)非結(jié)構(gòu)化數(shù)據(jù)(文檔)的查找問(wèn)題?怎樣按照關(guān)鍵詞找到相應(yīng)的文檔呢?關(guān)鍵詞查詢包含<關(guān)鍵詞>的文檔是哪一個(gè)?有多少個(gè)?怎樣找?怎樣快速地找?一、為什么要研究排序問(wèn)題待求解問(wèn)題的理解為什么要研究排序算法--非結(jié)構(gòu)化的數(shù)據(jù)文檔查找問(wèn)題(2)索引與倒排索引--需要排序?怎樣按照關(guān)鍵詞找到相應(yīng)的文檔呢?對(duì)所有文檔建立關(guān)鍵詞查詢查找文檔關(guān)鍵詞索引表倒排索引正排：一個(gè)文檔包含了哪些詞匯?#Doc1,{Word1,Word2,…}倒排：一個(gè)詞匯包含在哪些文檔中

Word1,{#Doc1,#Doc2,…}怎樣建立索引?怎樣利用索引快速地找?排序or不排序?一、為什么要研究排序問(wèn)題待求解問(wèn)題的理解為什么要研究排序算法--非結(jié)構(gòu)化的數(shù)據(jù)文檔查找問(wèn)題(3)關(guān)鍵詞的提取--需要排序?關(guān)鍵詞索引表倒排索引文檔能否自動(dòng)找出文檔中的關(guān)鍵詞?哪些是關(guān)鍵詞?排序or不排序?一、為什么要研究排序問(wèn)題待求解問(wèn)題的理解為什么要研究排序算法--非結(jié)構(gòu)化的數(shù)據(jù)文檔查找問(wèn)題(4)小結(jié)?非結(jié)構(gòu)化數(shù)據(jù)(文檔)的查找與搜索也需要排序怎樣按照關(guān)鍵詞找到相應(yīng)的文檔呢?對(duì)所有文檔建立關(guān)鍵詞查詢查找文檔關(guān)鍵詞索引表倒排索引文檔怎樣快速找到關(guān)鍵詞呢?哪些是關(guān)鍵詞呢?一、為什么要研究排序問(wèn)題待求解問(wèn)題的理解為什么要研究排序算法--非結(jié)構(gòu)化的數(shù)據(jù)文檔查找問(wèn)題(4)小結(jié)?非結(jié)構(gòu)化數(shù)據(jù)(文檔)的查找與搜索也需要排序怎樣按照關(guān)鍵詞找到相應(yīng)的文檔呢?對(duì)所有文檔建立關(guān)鍵詞查詢查找文檔關(guān)鍵詞索引表倒排索引文檔怎樣快速找到關(guān)鍵詞呢?哪些是關(guān)鍵詞呢?排序：字母序排序：數(shù)值序查找：反復(fù)進(jìn)行不同類(lèi)別的查找，不同類(lèi)別的排序一、為什么要研究排序問(wèn)題待求解問(wèn)題的理解第10章受限資源約束下的算法—排序問(wèn)題求解示例一、為什么要研究排序問(wèn)題待求解問(wèn)題的理解二、基本排序算法三、PageRank排序--排序問(wèn)題的不同思考方法本章導(dǎo)圖類(lèi)似于打撲克牌時(shí)，一邊抓牌，一邊理牌的過(guò)程：每抓一張牌就把它插入到適當(dāng)?shù)奈恢?；牌抓完了，也理完了。這種策略被稱(chēng)為插入排序基本排序算法I--內(nèi)排序之插入法排序二、基本排序算法1274978193366505180i=2i=3i=4i=512345678910Ai=57124978193366505180A7124978193366505180A7124978193366505180A7121949783366505180A7121933495051667880Ai=9…i=57124978783366505180Ai=57124949783366505180A插入排序:遞增排序示意.其中三角形左側(cè)為已排好序的元素,其右側(cè)為未排序的元素,實(shí)心三角形本身為待插入的元素.圖中示意了為待排序元素19騰挪空間的過(guò)程,由箭頭示意.空心三角形表示新插入的元素二、基本排序算法INSERTION-SORT(A)1.fori=2toN2.{key=A[i];3. j=i-1;4. While(j>0andA[j]>key)do5. {A[j+1]=A[j];6. j=j-1;}7. A[j+1]=key;8.} O(N2)

二、基本排序算法基本排序算法I--內(nèi)排序之插入法排序首先在所有數(shù)組元素中找出最小值的元素，放在A[1]中；接著在不包含A[1]的余下的數(shù)組元素中再找出最小值的元素，放置在A[2]中；如此下去，一直到最后一個(gè)元素。這一排序策略被稱(chēng)為簡(jiǎn)單選擇排序?；九判蛩惴↖I--內(nèi)排序之簡(jiǎn)單選擇法排序二、基本排序算法12

749

78193366505180i=1i=3i=412345678910A71249

78193366505180A71219

78493366505180A7121933495051667880Ai=9…i=471219

78493366505180Ai=471219

33497866505180A(b)選擇排序:遞增排序示意.其中三角形代表本輪要找的最小元素應(yīng)在的位置,方形代表本輪次至今為止所找到的最小元素所在位置,三角形左側(cè)為已排好序的元素,三角形右側(cè)的每一元素依次和方形位置元素比較.實(shí)線雙向箭頭代表兩個(gè)元素交換.虛線雙向箭頭代表兩個(gè)元素需要比較基本排序算法II--內(nèi)排序之簡(jiǎn)單選擇法排序(2)簡(jiǎn)單選擇排序的過(guò)程模擬?基本排序算法II--內(nèi)排序之簡(jiǎn)單選擇法排序二、基本排序算法SELECTION-SORT(A)1.fori=1toN-12.{ k=i;3．

forj=i+1toN4. {ifA[j]<A[k]thenk=j;}5. ifk<>ithen6. {7. temp=A[k];8. A[k]=A[i];9. A[i]=temp;10. }11.} O(N2)

基本排序算法II--內(nèi)排序之簡(jiǎn)單選擇法排序二、基本排序算法一個(gè)輪次一個(gè)輪次的處理。在每一輪次中依次對(duì)待排序數(shù)組元素中相鄰的兩個(gè)元素進(jìn)行比較，將大的放前，小的放后--遞減排序(或者是將小的放前，大的放后--遞增排序)。當(dāng)沒(méi)有交換時(shí)，則數(shù)據(jù)已被排好序。二、基本排序算法基本排序算法III--內(nèi)排序之冒泡法排序12

7

49

78

1933665051

80i=112

497

78

1933665051

80j=1i=1j=212

49787

1933665051

80i=1j=3…12

497819336650517

80i=1j=9i=9j=180

7866515049331912

712345678910AAAAA…12

4978193366505180

7i=2j=1Ai=8j=178

8066515049331912

7A(c)冒泡排序:遞減排序示意，其中小圓點(diǎn)代表本輪本次比較的兩個(gè)元素,雙向弧線箭頭代表兩個(gè)元素要相互交換12

7

49

78

1933665051

80Ai=1j=4二、基本排序算法BUBBLE-SORT(A)1.fori=1toN-12.{haschange=false;3. forj=1toN-i4. {ifA[j]<A[j+1]then5. {temp=A[j];6. A[j]=A[j+1];7. A[j+1]=temp;8. haschange=true;9. }10. }11.if(haschange==false)thenbreak;12.} O(N2)

二、基本排序算法內(nèi)排序問(wèn)題:待排序的數(shù)據(jù)可一次性地裝入內(nèi)存中，即排序者可以完整地看到和操縱所有數(shù)據(jù)，使用數(shù)組或其他數(shù)據(jù)結(jié)構(gòu)便可進(jìn)行統(tǒng)一的排序處理的排序問(wèn)題；外排序問(wèn)題:待排序的數(shù)據(jù)保存在磁盤(pán)上，不能一次性裝入內(nèi)存，即排序者不能一次完整地看到和操縱所有數(shù)據(jù)，需要將數(shù)據(jù)分批裝入內(nèi)存分批處理的排序問(wèn)題；問(wèn)題類(lèi)比：某教師要對(duì)學(xué)生按身高排序。教師只能在房間(相當(dāng)于內(nèi)存)中對(duì)學(xué)生進(jìn)行排序，假設(shè)房間僅能容納100人，那么對(duì)于小于100人的學(xué)生排序便屬于內(nèi)排序問(wèn)題。而對(duì)于大于100人，如1000人的學(xué)生排序，學(xué)生并不能都進(jìn)入房間，而只能在操場(chǎng)(相當(dāng)于磁盤(pán))等候，輪流進(jìn)入房間，這樣的排序便屬于外排序問(wèn)題。受限資源約束下的算法--內(nèi)排序與外排序問(wèn)題(1)排序問(wèn)題的復(fù)雜性在哪里?受限資源約束下的算法—內(nèi)排序與外排序問(wèn)題二、基本排序算法受限資源約束下的算法--內(nèi)排序與外排序問(wèn)題(2)外排序環(huán)境與問(wèn)題示例?內(nèi)存:2GB待排序數(shù)據(jù):7GB,10GB,100GB?--大數(shù)據(jù)集合這種需要使用硬盤(pán)等外部存儲(chǔ)設(shè)備進(jìn)行大數(shù)據(jù)集合排序的過(guò)程/算法稱(chēng)為外排序(Externalsorting)

。二、基本排序算法外排序算法的環(huán)境/資源(僅介紹思想,忽略一些細(xì)節(jié)),假設(shè):讀寫(xiě)磁盤(pán)塊函數(shù):ReadBlock,WriteBlock內(nèi)存大小:共Bmemory=6塊,每塊可裝載Rblock=5個(gè)元素待排序數(shù)據(jù):Rproblem=60個(gè)元素,共占用Bproblem=12塊問(wèn)題:Bproblem塊的數(shù)據(jù)怎樣利用Bmemory塊的內(nèi)存進(jìn)行排序?二、基本排序算法基本排序策略

Bproblem塊數(shù)據(jù)可劃分為N個(gè)子集合,使每個(gè)子集合的塊數(shù)小于內(nèi)存可用塊數(shù)，即：Bproblem/N<Bmemory。每個(gè)子集合都可裝入內(nèi)存并采用內(nèi)排序算法排好序并重新寫(xiě)回磁盤(pán)。問(wèn)題轉(zhuǎn)化為:N個(gè)已排序子集合的數(shù)據(jù)怎樣利用內(nèi)存進(jìn)行總排序?Bmemory=6塊,Rblock=5個(gè)元素Rproblem=60個(gè)元素

Bproblem=12塊二、基本排序算法子集合已排好序，如何進(jìn)行總排序內(nèi)存不能裝下所有子集合二、基本排序算法磁盤(pán)內(nèi)存Bmemory=6第1塊第2塊第3塊第4塊第5塊第6塊子集合存儲(chǔ)在磁盤(pán)上的若干塊二、基本排序算法N個(gè)子集合各自依次序讀取一塊裝入內(nèi)存內(nèi)存中的N塊(對(duì)應(yīng)N個(gè)子集合)各自依次序讀取一個(gè)元素形成一個(gè)待比較集合將待比較集合中的最小元素取出寫(xiě)入輸出塊中輸出塊依序?qū)懟卮疟P(pán)上基本排序算法IV--外排序之多路歸并排序(3)基本歸并動(dòng)作?二、基本排序算法歸并排序--過(guò)程模擬(詳細(xì)介紹參見(jiàn)另一部份：過(guò)程模擬)基本排序算法IV--外排序之多路歸并排序(4)過(guò)程模擬?二、基本排序算法歸并排序--算法描述二、基本排序算法908682807555453530278078726252727068646270605843322420181009504238343160454238352815110805080806040329191613102520150908050310080504100805061008080610080808100803030403040503040506030405060803040506080808100908081009080910091109100908080808080808080809內(nèi)存磁盤(pán)2815110805080806040329191613102520150908寫(xiě)磁盤(pán)讀磁盤(pán)

24201810092420181009二、基本排序算法歸并排序--過(guò)程模擬基本排序算法IV--外排序之多路歸并排序的過(guò)程模擬(2)過(guò)程模擬小結(jié)?二、基本排序算法算法的效率：讀寫(xiě)磁盤(pán)塊的次數(shù)，即I/O數(shù)=4Bproblem

子集合排序階段讀一遍寫(xiě)一遍2Bproblem歸并階段讀一遍寫(xiě)一遍2Bproblem二、基本排序算法大數(shù)據(jù)集塊數(shù)>Bmemory2如何排序呢？算法的應(yīng)用條件：子集合數(shù)<Bmemory子集合的塊數(shù)<Bmemory

即大數(shù)據(jù)集塊數(shù)<Bmemory2二、基本排序算法內(nèi)存大小:共Bmemory=3塊待排序數(shù)據(jù):

共占用Bproblem=30塊基本策略:30塊的數(shù)據(jù)集

10個(gè)子集合，每個(gè)子集合3塊，排序并存儲(chǔ)。10個(gè)已排序子集合分成5個(gè)組：每個(gè)組2個(gè)子集合,分別進(jìn)行二路歸并，則可得到5個(gè)排好序的集合；5個(gè)集合再分成3個(gè)組：每個(gè)組2個(gè)子集，剩余一個(gè)單獨(dú)1組，分別進(jìn)行二路歸并，可得3個(gè)排好序的集合；再分組，再歸并得到2個(gè)排好序的集合；再歸并便可完成最終的排序。二、基本排序算法更大數(shù)據(jù)集如何應(yīng)用多路歸并排序算法歸并排序--思考假如內(nèi)存共有8塊，問(wèn)其如何排序有70塊的數(shù)據(jù)集呢？你是采用二路歸并、三路歸并、…、七路歸并？你設(shè)計(jì)的具體算法，磁盤(pán)讀寫(xiě)次數(shù)是多少呢？磁盤(pán)讀寫(xiě)次數(shù)最少的應(yīng)是幾路歸并？基本排序算法IV-續(xù)--外排序之多路歸并排序-討論(4)思考一下下列情況排序，應(yīng)該怎么辦?二、基本排序算法第10章受限資源約束下的算法—排序問(wèn)題求解示例一、為什么要研究排序問(wèn)題待求解問(wèn)題的理解二、基本排序算法三、PageRank排序--排序問(wèn)題的不同思考方法本章導(dǎo)圖4,540,000條檢索記錄1,210,000條檢索記錄怎樣把最重要的檢索記錄顯示給用戶?問(wèn)題背景搜索引擎三、PageRank排序--排序問(wèn)題的不同思考方法<標(biāo)記>文本</標(biāo)記><AHREF=“/realcorp/products.html”>OurProductInformation</A>

<AHREF=“鏈接到另一個(gè)網(wǎng)頁(yè)的地址”>OurProductInformation</A>網(wǎng)頁(yè)重要嗎?網(wǎng)頁(yè)重要度問(wèn)題背景網(wǎng)頁(yè)P(yáng)ageRank是計(jì)算網(wǎng)頁(yè)重要度的一種方法三、PageRank排序--排序問(wèn)題的不同思考方法網(wǎng)頁(yè)重要度問(wèn)題的抽象正向鏈接反向鏈接一個(gè)網(wǎng)頁(yè)的正向鏈接是另一個(gè)網(wǎng)頁(yè)的反向鏈接PageRank網(wǎng)頁(yè)排序算法I--網(wǎng)頁(yè)排序問(wèn)題及思想(3)正向鏈接與反向鏈接?基于這些信息，如何計(jì)算網(wǎng)頁(yè)重要度?三、PageRank排序--排序問(wèn)題的不同思考方法關(guān)于網(wǎng)頁(yè)的基本觀點(diǎn)網(wǎng)頁(yè)的反向鏈接數(shù)越多是否越重要呢?重要度越高的反向鏈接是否越重要呢?正向鏈接數(shù)越多，是否其對(duì)鏈接的網(wǎng)頁(yè)而言,重要度會(huì)降低呢?三、PageRank排序--排序問(wèn)題的不同思考方法網(wǎng)頁(yè)重要度一個(gè)網(wǎng)頁(yè)的重要度等于其所有反向鏈接的加權(quán)和，即：反向鏈接權(quán)值z(mì)i,網(wǎng)頁(yè)重要度R,則

R=zi(for所有反向鏈接i)。一個(gè)正向鏈接的權(quán)值等于網(wǎng)頁(yè)的重要度除以其正向鏈接數(shù),即：網(wǎng)頁(yè)重要度R,其正向鏈接數(shù)m,則其每一個(gè)正向鏈接的權(quán)值 z=R/m。三、PageRank排序--排序問(wèn)題的不同思考方法PageRank的數(shù)學(xué)表達(dá)示意圖PageRank的概念示意圖三、PageRank排序--排序問(wèn)題的不同思考方法PageRank網(wǎng)頁(yè)排序算法II--網(wǎng)頁(yè)排序問(wèn)題的表達(dá)與建模(1)問(wèn)題的數(shù)學(xué)建模?數(shù)學(xué)建模--示例三、PageRank排序--排序問(wèn)題的不同思考方法數(shù)學(xué)建模--鄰接矩陣行i，列j均是網(wǎng)頁(yè)編號(hào)正向鏈接反向鏈接正向鏈接反向鏈接PageRank網(wǎng)頁(yè)排序算法II--網(wǎng)頁(yè)排序問(wèn)題的表達(dá)與建模(1)問(wèn)題的數(shù)學(xué)建模?三、PageRank排序--排序問(wèn)題的不同思考方法數(shù)學(xué)建?！D(zhuǎn)移概率反向鏈接轉(zhuǎn)移概率矩陣反向鏈接的權(quán)值網(wǎng)頁(yè)重要度向量鄰接矩陣PageRank網(wǎng)頁(yè)排序算法II--網(wǎng)頁(yè)排序問(wèn)題的表達(dá)與建模(2)正向鏈接的權(quán)值矩陣轉(zhuǎn)移概率?三、PageRank排序--排序問(wèn)題的不同思考方法PageRank網(wǎng)頁(yè)排序算法III--網(wǎng)頁(yè)重要度的迭代計(jì)算方法及討論(1)網(wǎng)頁(yè)重要度的迭代計(jì)算方法?轉(zhuǎn)移概率矩陣M網(wǎng)頁(yè)i的重要度為Ri，各網(wǎng)頁(yè)重要度的向量R，記為： R=(R1,R2

…,Rn)T

迭代計(jì)算Ri(1)=

j(M[i][j]*Rj(0))Ri(2)=

j(M[i][j]*Rj(1))…

…Ri(n)=

j(M[i][j]*Rj(n-1))Ri(n)=Ri(n-1)???R的初始值是多少呢?從哪一個(gè)Ri開(kāi)始計(jì)算呢?矩陣乘法第n-1次的網(wǎng)頁(yè)重要度第n次的網(wǎng)頁(yè)重要度=三、PageRank排序--排序問(wèn)題的不同思考方法PageRank—計(jì)算結(jié)果分析PageRank網(wǎng)頁(yè)排序算法III--網(wǎng)頁(yè)重要度的迭代計(jì)算方法及討論(2)PageRank的計(jì)算結(jié)果分析?1號(hào)vs.5號(hào)6號(hào)vs.7號(hào)2號(hào)vs.3號(hào)三、PageRank排序--排序問(wèn)題的不同思考方法PageRank網(wǎng)頁(yè)排序算法IVRank與數(shù)學(xué)及算法總結(jié)(1)PageRank計(jì)算vs.數(shù)學(xué)的特征方程?迭代計(jì)算網(wǎng)頁(yè)重要度R(0)=(R1(0),R2(0)

…,Rn(0))TR(1)=cMR(0)R(2)=cMR(1)…R=R(n)=R(n-1)，當(dāng)R不發(fā)生變化時(shí)，即收斂時(shí)則為所求網(wǎng)頁(yè)重要度的迭代計(jì)算對(duì)N階方陣A(轉(zhuǎn)移概率矩陣)，滿足：

Ax=

x的數(shù)λ稱(chēng)為A的特征值，稱(chēng)x為屬于λ的特征向量。通過(guò)數(shù)學(xué)學(xué)習(xí)求解方法三、PageRank排序--排序問(wèn)題的不同思考方法網(wǎng)頁(yè)排序：網(wǎng)頁(yè)重要度計(jì)算網(wǎng)頁(yè)鏈接：正向鏈接與反向鏈接求解思想：求穩(wěn)定性數(shù)學(xué)的語(yǔ)義：特征方程表達(dá)成數(shù)學(xué)：0,1矩陣權(quán)值矩陣—轉(zhuǎn)移概率矩陣從問(wèn)題語(yǔ)義挖掘求解思想：反向鏈接數(shù)越多越重要；反向鏈接有權(quán)值；反向鏈接的權(quán)值確定：網(wǎng)頁(yè)重要度按其正向鏈接的個(gè)數(shù)進(jìn)行分配網(wǎng)頁(yè)重要度計(jì)算：PageRankPageRank網(wǎng)頁(yè)排序算法IVRank與數(shù)學(xué)及算法總結(jié)(2)PageRank算法總結(jié)?三、PageRank排序--排序問(wèn)題的不同思考方法第11章難解性問(wèn)題求解—組合、隨機(jī)與近似解第11章難解性問(wèn)題求解—組合、隨機(jī)與近似解一、可求解與難求解問(wèn)題二、從社會(huì)/自然中尋求問(wèn)題求解的思想--生物學(xué)中的遺傳與進(jìn)化三、將社會(huì)/自然思想應(yīng)用于計(jì)算--遺傳算法的簡(jiǎn)單示例四、探討算法的本質(zhì)--遺傳算法為什么可以求解NP問(wèn)題？五、算法研究的根本是問(wèn)題求解--組合優(yōu)化問(wèn)題及遺傳算法求解本章導(dǎo)圖怎樣研究算法：研究什么算法一、可求解與難求解問(wèn)題遺傳算法蟻群算法蜂群算法…

算法社會(huì)/自然現(xiàn)象(遺傳與進(jìn)化)計(jì)算學(xué)科的(遺傳)算法(遺傳)算法的本質(zhì)(遺傳)算法的應(yīng)用本章內(nèi)容組織思路一、可求解與難求解問(wèn)題社會(huì)/自然現(xiàn)象(遺傳與進(jìn)化)計(jì)算學(xué)科的(遺傳)算法(遺傳)算法的本質(zhì)(遺傳)算法的應(yīng)用本章內(nèi)容組織思路生物學(xué)中的問(wèn)題求解思想生物學(xué)中的問(wèn)題求解過(guò)程/步驟計(jì)算學(xué)科中的問(wèn)題求解過(guò)程/步驟NPC類(lèi)問(wèn)題NPC類(lèi)問(wèn)題的解過(guò)程/步驟中的設(shè)計(jì)技巧具體問(wèn)題一、可求解與難求解問(wèn)題社會(huì)/自然現(xiàn)象(遺傳與進(jìn)化)計(jì)算學(xué)科的(遺傳)算法(遺傳)算法的本質(zhì)(遺傳)算法的應(yīng)用本章內(nèi)容組織思路計(jì)算與計(jì)算系統(tǒng)(淺層次)社會(huì)/自然/生活計(jì)算與計(jì)算系統(tǒng)(深層次)由遺傳算法的學(xué)習(xí)，學(xué)會(huì)算法的研究，更重要的是養(yǎng)成科學(xué)研究良好的習(xí)慣本質(zhì)應(yīng)用寬度學(xué)習(xí)深度學(xué)習(xí)一、可求解與難求解問(wèn)題現(xiàn)實(shí)世界中的問(wèn)題分類(lèi)計(jì)算機(jī)在有限時(shí)間內(nèi)能夠求解的(可求解問(wèn)題)計(jì)算機(jī)在有限時(shí)間內(nèi)不能求解的(難求解問(wèn)題)計(jì)算機(jī)完全不能求解的(不可計(jì)算問(wèn)題)【計(jì)算復(fù)雜性】是指問(wèn)題的一種特性，是指求問(wèn)題精確解的算法的復(fù)雜性，衡量利用計(jì)算機(jī)求解問(wèn)題的難易程度。計(jì)算所需的步數(shù)或指令條數(shù)，即時(shí)間復(fù)雜度計(jì)算所需的存儲(chǔ)空間大小，即空間復(fù)雜度--通常表達(dá)為關(guān)于問(wèn)題規(guī)模n的一個(gè)函數(shù)O(f(n))問(wèn)題的計(jì)算復(fù)雜性問(wèn)題的計(jì)算復(fù)雜性一、可求解與難求解問(wèn)題問(wèn)題規(guī)模n計(jì)算量1010！2020！100100！10001000！1000010000！20！=1.216×1017203=

8000O(n3)O(3n)0.2秒4

1028秒=1015年注：每秒百萬(wàn)次，n=60，1015年相當(dāng)于10億臺(tái)計(jì)算機(jī)計(jì)算一百萬(wàn)年O(n!)與O(n3)、O(n3)與O(3n)的差別O(bn),O(n!)O(1),O(logn),O(n),O(nlogn),O(nb)什么是有限時(shí)間內(nèi)不能求解一、可求解與難求解問(wèn)題【P類(lèi)問(wèn)題】多項(xiàng)式問(wèn)題(PolynomialProblem)，即：可以找出一個(gè)呈現(xiàn)O(na)復(fù)雜性算法求出精確解的問(wèn)題，其中a為常數(shù)。P類(lèi)問(wèn)題是指計(jì)算機(jī)可以在有限時(shí)間內(nèi)求出精確解的問(wèn)題，【NP類(lèi)問(wèn)題】非確定性多項(xiàng)式問(wèn)題(Non-deterministicPolynomial)，即：可以找出一個(gè)呈現(xiàn)O(na)復(fù)雜性算法來(lái)驗(yàn)證一個(gè)解是否正確的非確定性問(wèn)題。有些問(wèn)題，其答案無(wú)法直接計(jì)算得到，但可通過(guò)間接的猜算/試算來(lái)得到，這就是非確定性問(wèn)題(Non-deterministic)。雖然在多項(xiàng)式時(shí)間內(nèi)難于求解，但給定一個(gè)解卻不難在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證其正確性的問(wèn)題，即是NP類(lèi)問(wèn)題。【NPC類(lèi)問(wèn)題】完全非確定性多項(xiàng)式問(wèn)題(NP-Complete)，即：如果NP問(wèn)題的所有可能解都可以在多項(xiàng)式時(shí)間內(nèi)進(jìn)行正確與否的驗(yàn)算，則為NP-Complete問(wèn)題。一個(gè)NP問(wèn)題，并非其每個(gè)解都可以在多項(xiàng)式時(shí)間內(nèi)驗(yàn)算，即：有些解是可以驗(yàn)算的，而有些解是不能驗(yàn)算的。如果一個(gè)NP問(wèn)題其需要驗(yàn)算的解空間是用非多項(xiàng)式函數(shù)(指數(shù)函數(shù)或階乘函數(shù))來(lái)表達(dá)的，則是NP-Complete問(wèn)題。如果一個(gè)NP問(wèn)題經(jīng)過(guò)約簡(jiǎn)后得到的問(wèn)題仍舊是NP問(wèn)題，則是NP-Complete問(wèn)題問(wèn)：加密算法應(yīng)該設(shè)計(jì)成一個(gè)什么問(wèn)題呢？怎樣以復(fù)雜性來(lái)劃分問(wèn)題一、可求解與難求解問(wèn)題窮舉法或稱(chēng)遍歷法：對(duì)解空間中的每一個(gè)可能解進(jìn)行驗(yàn)證，直到所有的解都被驗(yàn)證是否正確，便能得到精確的結(jié)果精確解可能是O(n!)或O(an)近似解求解算法近似解應(yīng)該是O(n