大學計算機-計算思維與信息素養(yǎng) 課件 第9章 算法：程序與計算系統(tǒng)的靈魂 - 第15章 第20講-深度學習是怎樣提高智能的-神經網絡與深度學習

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

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

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

,由節(jié)點和邊所構成的一種結構。由一個節(jié)點出發(fā)，又回到原出發(fā)節(jié)點，則連接該節(jié)點的邊數是否應為偶數?這個問題無解！無解的問題還用構造算法嗎?陸地--

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

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

“可達從一個節(jié)點出發(fā)能夠到達另一個節(jié)點”

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

將TSP問題抽象為數學問題

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

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

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

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

，Q是某些邏輯條件，即按條件判斷結果決定執(zhí)行哪些規(guī)則的一種結構。循環(huán)結構：控制指令或規(guī)則的多次執(zhí)行的一種結構迭代(iteration)循環(huán)結構又分為有界循環(huán)結構和條件循環(huán)結構。有界循環(huán)：“執(zhí)行A指令N次”，其中N是一個整數。條件循環(huán)：某些時候稱為無界循環(huán)，“重復執(zhí)行A直到條件Q成立”或“當Q成立時反復執(zhí)行A”，其中Q是條件。算法與程序的基本控制結構算法的類自然語言表達方法四、算法設計算法思想的精確表達Startofthealgorithm(算法開始)(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的結果。Endofthealgorithm(算法結束)

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

矩形框：表示一組順序執(zhí)行的規(guī)則或者程序語句。菱形框：表示條件判斷，并根據判斷結果執(zhí)行不同的分支。圓形框：表示算法或程序的開始或結束。箭頭線：表示算法或程序的走向。算法的程序流程圖表達方法四、算法設計算法思想的精確表達三種控制結構的流程圖表達開始第1條規(guī)則或語句第n條規(guī)則或語句結束順序結構的流程圖開始條件成立否？是否條件成立時執(zhí)行的規(guī)則或語句結束條件不成立時執(zhí)行的規(guī)則或語句分支結構的流程圖循環(huán)結構的流程圖初始化部分開始循環(huán)控制條件成立？修改部分需循環(huán)執(zhí)行的規(guī)則或語句。即：循環(huán)體結束是否循環(huán)結束算法的程序流程圖表達方法四、算法設計算法思想的精確表達循環(huán)結構的兩種情況的流程圖表達初始化部分開始循環(huán)控制條件成立？修改部分需循環(huán)執(zhí)行的規(guī)則或語句結束是否循環(huán)結束有界循環(huán)結構的流程圖(循環(huán)次數確定)初始化部分開始循環(huán)控制條件成立？修改部分需循環(huán)執(zhí)行的規(guī)則或語句結束否循環(huán)未結束是條件循環(huán)結構的流程圖(循環(huán)次數不確定)算法的程序流程圖表達方法四、算法設計算法思想的精確表達【示例】歐幾里德算法流程圖示例四、算法設計算法思想的精確表達求解TSP問題的遍歷算法的表達當前最短路徑MS設為空，當前最短距離DTemp設為最大值開始所有路徑組合完畢否？結束否是組合一條新路徑S并計算該路徑的距離Distance比當前最短距離小嗎？將該路徑記錄為當前最短路徑，并用其距離值更新當前最短距離輸出當前最短路徑及當前最短距離是否將思想/策略轉變?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當前最短路徑1234MS當前最短距離DTemp四、算法設計算法思想的精確表達求解TSP問題的貪心算法的表達依次訪問過的城市編號被記錄在S[1],S[2],…,S[N}中,即第I次訪問的城市記錄在S[I]中。Step(1)：從1號城市開始訪問，將城市編號1賦值給S[1]。Step(6)：第I次訪問的城市為城市j，其距第I-1次訪問的城市的距離最短。StartoftheAlgorithm(1)S[1]=1;(2)Sum=0;(3)初始化距離數組D[N,N];(4)I=2;(5)從所有未訪問過的城市中查找距離S[I-1]最近的城市j;(6)S[I]=j;(7)I=I+1;(8)Sum=Sum+Dtemp;(9)如果I<=N，轉步驟(5)，否則，轉步驟(10);(10)Sum=Sum+D[1,j]；(11)逐個輸出S[N]中的全部元素;(12)輸出Sum。EndoftheAlgorithmD1

SS[1]S[2]S[3]S[4]I=2,3,4當前要找第幾個j=1,

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

(5.3)L=1；

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

(5.5)L=L+1；

(5.6)如果L<I，轉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，轉步驟5.3。1

SS[1]S[2]S[3]S[4]K=2,3,4城市號L=1,

2,…,I-1從第1個訪問過的，到第I-1個訪問過的I=2,3,4當前要找第幾個四、算法設計算法思想的精確表達求解TSP問題的貪心算法的表達1

SS[1]S[2]S[3]S[4]K=2,3,4城市號L=1,

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

編譯

鏈接

執(zhí)行。一套書寫程序的語法規(guī)則計算機語言程序設計環(huán)境：編輯、編譯、連接、調試、運行一體化平臺高級語言程序目標程序可執(zhí)行程序編輯程序編譯程序連接程序公用函數庫調試程序五、算法的實現(xiàn)--算法的程序設計算法的實現(xiàn)環(huán)境與過程SS[0]S[1]S[2]S[3]K從1,…,n-1是城市的編號I是至今已訪問過的城市數S[0]至S[I-1]中存儲的是已訪問過的城市的編號main(){…//前面已為K和I賦過值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)過

}else{//城市K出現(xiàn)過}...}判斷城市K是否是已訪問過的城市1432實現(xiàn)算法的程序：閱讀與理解五、算法的實現(xiàn)--算法的程序設計SS[0]S[1]S[2]S[3]K從1,…,n-1是城市的編號I是至今已訪問過的城市數S[I-1]中存儲的是當前訪問過的城市編號，要找第I個程序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;…}尋找下一個未訪問過的城市j,且其距當前訪問城市S[I-1]距離最短1432D[K][S[I-1]]為城市K距當前訪問過的城市的距離實現(xiàn)算法的程序：閱讀與理解五、算法的實現(xiàn)--算法的程序設計實現(xiàn)算法的程序：閱讀與理解TSP問題的貪心算法程序實例五、算法的實現(xiàn)--算法的程序設計第9章算法：程序與計算系統(tǒng)的靈魂一、算法的基本概念二、建立問題的數學模型數學建模三、算法策略選擇算法思想四、算法設計算法思想的精確表達五、算法的實現(xiàn)--算法的程序設計六、算法的模擬與分析本章導圖算法的正確性問題問題求解的過程、方法——算法是正確的嗎？算法的輸出是問題的解嗎？滿足問題求解約束的解就是問題的解，但不一定是最優(yōu)解。20世紀60年代，美國一架發(fā)往金星的航天飛機由于控制程序出錯而永久丟失在太空中。算法的效果評價算法的輸出是最優(yōu)解還是可行解？如果是可行解，與最優(yōu)解的偏差多大？兩種評價方法：證明方法：利用數學方法證明；仿真分析方法：產生或選取大量的、具有代表性的問題實例，利用該算法對這些問題實例進行求解，并對算法產生的結果進行統(tǒng)計分析。算法獲得的解是最優(yōu)的嗎?六、算法的模擬與分析算法的模擬與分析算法是正確的嗎?TSP問題貪心算法的正確性評價直觀上只需檢查算法的輸出結果中，每個城市出現(xiàn)且僅出現(xiàn)一次，該結果即是TSP問題的可行解，說明算法正確地求解了這些問題實例1234SS[1]S[2]S[3]S[4]六、算法的模擬與分析TSP問題貪心算法的效果評價如果實例的最優(yōu)解已知（問題規(guī)模小或問題已被成功求解），利用統(tǒng)計方法對若干問題實例的算法結果與最優(yōu)解進行對比分析，即可對其進行效果評價；對于較大規(guī)模的問題實例，其最優(yōu)解往往是未知的，因此，算法的效果評價只能借助于與前人算法結果的比較。1234SS[1]S[2]S[3]S[4]六、算法的模擬與分析時間復雜性:如果一個問題的規(guī)模是n，解這一問題的某一算法所需要的時間為T(n)，它是n的某一函數，則T(n)稱為這一算法的“時間復雜性”?！按驩記法”：基本參數n——問題實例的規(guī)模把復雜性或運行時間表達為n的函數。“O”表示量級(order)，允許使用“=”代替“≈”，如n2+n+1=Ο(n2)?？臻g復雜性：算法在執(zhí)行過程中所占存儲空間的大小。算法獲得結果的時間有多長?算法復雜性O(f(n))算法的時間復雜度與空間復雜度六、算法的模擬與分析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)主要關注點：循環(huán)的層數算法復雜性分析示例六、算法的模擬與分析TSP問題貪心算法的復雜性分析nn2n3一個關于n的三重循環(huán)。時間復雜度是O(n3)。六、算法的模擬與分析TSP問題遍歷算法的復雜性分析列出每一條可供選擇的路線，計算出每條路線的總里程，最后從中選出一條最短的路線。路徑組合數目為(n-1)!時間復雜度是O((n-1)!)當前最短路徑設為空，當前最短距離設為最大值開始所有路徑組合完畢否？結束否是組合一條新路徑并計算該路徑的距離比當前最短距離小嗎？將該路徑記錄為當前最短路徑，并用其距離值更新當前最短距離輸出當前最短路徑及當前最短距離是否六、算法的模擬與分析問題規(guī)模n計算量1010！2020！100100！10001000！1000010000！20！=1.216×1017203=

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

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

O(n3)

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

精確解|滿意解：?充分小時的近似解TSP問題的遍歷算法(又稱窮舉或蠻干)TSP問題的貪心算法TSP問題的計算復雜性與算法復雜性TSP問題的計算復雜度：

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

對一組“商品”，按“價格”排序；

對一組“網頁”，按“重要度”排序；

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

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

Word1,{#Doc1,#Doc2,…}怎樣建立索引?怎樣利用索引快速地找?排序or不排序?一、為什么要研究排序問題待求解問題的理解為什么要研究排序算法--非結構化的數據文檔查找問題(3)關鍵詞的提取--需要排序?關鍵詞索引表倒排索引文檔能否自動找出文檔中的關鍵詞?哪些是關鍵詞?排序or不排序?一、為什么要研究排序問題待求解問題的理解為什么要研究排序算法--非結構化的數據文檔查找問題(4)小結?非結構化數據(文檔)的查找與搜索也需要排序怎樣按照關鍵詞找到相應的文檔呢?對所有文檔建立關鍵詞查詢查找文檔關鍵詞索引表倒排索引文檔怎樣快速找到關鍵詞呢?哪些是關鍵詞呢?一、為什么要研究排序問題待求解問題的理解為什么要研究排序算法--非結構化的數據文檔查找問題(4)小結?非結構化數據(文檔)的查找與搜索也需要排序怎樣按照關鍵詞找到相應的文檔呢?對所有文檔建立關鍵詞查詢查找文檔關鍵詞索引表倒排索引文檔怎樣快速找到關鍵詞呢?哪些是關鍵詞呢?排序：字母序排序：數值序查找：反復進行不同類別的查找，不同類別的排序一、為什么要研究排序問題待求解問題的理解第10章受限資源約束下的算法—排序問題求解示例一、為什么要研究排序問題待求解問題的理解二、基本排序算法三、PageRank排序--排序問題的不同思考方法本章導圖類似于打撲克牌時，一邊抓牌，一邊理牌的過程：每抓一張牌就把它插入到適當的位置；牌抓完了，也理完了。這種策略被稱為插入排序基本排序算法I--內排序之插入法排序二、基本排序算法1274978193366505180i=2i=3i=4i=512345678910Ai=57124978193366505180A7124978193366505180A7124978193366505180A7121949783366505180A7121933495051667880Ai=9…i=57124978783366505180Ai=57124949783366505180A插入排序:遞增排序示意.其中三角形左側為已排好序的元素,其右側為未排序的元素,實心三角形本身為待插入的元素.圖中示意了為待排序元素19騰挪空間的過程,由箭頭示意.空心三角形表示新插入的元素二、基本排序算法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--內排序之插入法排序首先在所有數組元素中找出最小值的元素，放在A[1]中；接著在不包含A[1]的余下的數組元素中再找出最小值的元素，放置在A[2]中；如此下去，一直到最后一個元素。這一排序策略被稱為簡單選擇排序。基本排序算法II--內排序之簡單選擇法排序二、基本排序算法12

749

78193366505180i=1i=3i=412345678910A71249

78193366505180A71219

78493366505180A7121933495051667880Ai=9…i=471219

78493366505180Ai=471219

33497866505180A(b)選擇排序:遞增排序示意.其中三角形代表本輪要找的最小元素應在的位置,方形代表本輪次至今為止所找到的最小元素所在位置,三角形左側為已排好序的元素,三角形右側的每一元素依次和方形位置元素比較.實線雙向箭頭代表兩個元素交換.虛線雙向箭頭代表兩個元素需要比較基本排序算法II--內排序之簡單選擇法排序(2)簡單選擇排序的過程模擬?基本排序算法II--內排序之簡單選擇法排序二、基本排序算法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--內排序之簡單選擇法排序二、基本排序算法一個輪次一個輪次的處理。在每一輪次中依次對待排序數組元素中相鄰的兩個元素進行比較，將大的放前，小的放后--遞減排序(或者是將小的放前，大的放后--遞增排序)。當沒有交換時，則數據已被排好序。二、基本排序算法基本排序算法III--內排序之冒泡法排序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)冒泡排序:遞減排序示意，其中小圓點代表本輪本次比較的兩個元素,雙向弧線箭頭代表兩個元素要相互交換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)

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

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

Bproblem塊數據可劃分為N個子集合,使每個子集合的塊數小于內存可用塊數，即：Bproblem/N<Bmemory。每個子集合都可裝入內存并采用內排序算法排好序并重新寫回磁盤。問題轉化為:N個已排序子集合的數據怎樣利用內存進行總排序?Bmemory=6塊,Rblock=5個元素Rproblem=60個元素

Bproblem=12塊二、基本排序算法子集合已排好序，如何進行總排序內存不能裝下所有子集合二、基本排序算法磁盤內存Bmemory=6第1塊第2塊第3塊第4塊第5塊第6塊子集合存儲在磁盤上的若干塊二、基本排序算法N個子集合各自依次序讀取一塊裝入內存內存中的N塊(對應N個子集合)各自依次序讀取一個元素形成一個待比較集合將待比較集合中的最小元素取出寫入輸出塊中輸出塊依序寫回磁盤上基本排序算法IV--外排序之多路歸并排序(3)基本歸并動作?二、基本排序算法歸并排序--過程模擬(詳細介紹參見另一部份：過程模擬)基本排序算法IV--外排序之多路歸并排序(4)過程模擬?二、基本排序算法歸并排序--算法描述二、基本排序算法908682807555453530278078726252727068646270605843322420181009504238343160454238352815110805080806040329191613102520150908050310080504100805061008080610080808100803030403040503040506030405060803040506080808100908081009080910091109100908080808080808080809內存磁盤2815110805080806040329191613102520150908寫磁盤讀磁盤

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

子集合排序階段讀一遍寫一遍2Bproblem歸并階段讀一遍寫一遍2Bproblem二、基本排序算法大數據集塊數>Bmemory2如何排序呢？算法的應用條件：子集合數<Bmemory子集合的塊數<Bmemory

即大數據集塊數<Bmemory2二、基本排序算法內存大小:共Bmemory=3塊待排序數據:

共占用Bproblem=30塊基本策略:30塊的數據集

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

<AHREF=“鏈接到另一個網頁的地址”>OurProductInformation</A>網頁重要嗎?網頁重要度問題背景網頁PageRank是計算網頁重要度的一種方法三、PageRank排序--排序問題的不同思考方法網頁重要度問題的抽象正向鏈接反向鏈接一個網頁的正向鏈接是另一個網頁的反向鏈接PageRank網頁排序算法I--網頁排序問題及思想(3)正向鏈接與反向鏈接?基于這些信息，如何計算網頁重要度?三、PageRank排序--排序問題的不同思考方法關于網頁的基本觀點網頁的反向鏈接數越多是否越重要呢?重要度越高的反向鏈接是否越重要呢?正向鏈接數越多，是否其對鏈接的網頁而言,重要度會降低呢?三、PageRank排序--排序問題的不同思考方法網頁重要度一個網頁的重要度等于其所有反向鏈接的加權和，即：反向鏈接權值zi,網頁重要度R,則

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

…,Rn)T

迭代計算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的初始值是多少呢?從哪一個Ri開始計算呢?矩陣乘法第n-1次的網頁重要度第n次的網頁重要度=三、PageRank排序--排序問題的不同思考方法PageRank—計算結果分析PageRank網頁排序算法III--網頁重要度的迭代計算方法及討論(2)PageRank的計算結果分析?1號vs.5號6號vs.7號2號vs.3號三、PageRank排序--排序問題的不同思考方法PageRank網頁排序算法IVRank與數學及算法總結(1)PageRank計算vs.數學的特征方程?迭代計算網頁重要度R(0)=(R1(0),R2(0)

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

Ax=

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

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

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

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