算法設(shè)計(jì)與分析第1章 算法引論ppt課件

1、算法設(shè)計(jì)與分析*河南工程學(xué)院第1 章 算法引論 主要內(nèi)容 一、算法及其特性 二、算法的時(shí)間空間復(fù)雜度 三、算法分析(Algorithm Analysis) 1.分析算法時(shí)間復(fù)雜度的根本步驟 2.算法時(shí)間復(fù)雜度的有關(guān)概念 3.分析、求解算法復(fù)雜度的方法 四、迭代法 、遞歸算法設(shè)計(jì)與分析*河南工程學(xué)院1.1 算法1.2 算法描畫(huà)1.3 算法分析的根底1.4 根本數(shù)據(jù)構(gòu)造1.5 迭代法1.6 遞歸和消除遞歸算法設(shè)計(jì)與分析*河南工程學(xué)院 學(xué)習(xí)要求 掌握算法復(fù)雜度的根本概念 熟習(xí)算法復(fù)雜度分析的根本方法算法設(shè)計(jì)與分析*河南工程學(xué)院1.1 算法 一、算法(algorighm) 算法就是一組有窮的規(guī)那么，它

2、們規(guī)定理處理某一特定類(lèi)型問(wèn)題的一系列運(yùn)算算法設(shè)計(jì)與分析*河南工程學(xué)院 Gcd (int a, int b) 1 if ab 2 then swap (a,b) 3 na%b 4 while n0 5 do ab; 6 bn; 7 a%b; 8 return b;算法設(shè)計(jì)與分析*河南工程學(xué)院1.1 算法 二、算法的特點(diǎn) 1. 有窮性 2. 確定性 3. 輸入 4. 輸出 5. 能行性算法設(shè)計(jì)與分析*河南工程學(xué)院 程序是算法用某種程序設(shè)計(jì)言語(yǔ)的詳細(xì)實(shí)現(xiàn)。 程序可以不滿(mǎn)足算法的性質(zhì)(1)。 例如操作系統(tǒng)，是一個(gè)在無(wú)限循環(huán)中執(zhí)行的程序，因此不是一個(gè)算法。 操作系統(tǒng)的各種義務(wù)可看成是單獨(dú)的問(wèn)題，每一個(gè)問(wèn)

3、題由操作系統(tǒng)中的一個(gè)子程序經(jīng)過(guò)特定的算法來(lái)實(shí)現(xiàn)。該子程序得到輸出結(jié)果后便終止。算法設(shè)計(jì)與分析*河南工程學(xué)院1.2 算法的描畫(huà) 自然言語(yǔ) 流程圖 PAD圖 盒圖 偽代碼 計(jì)算機(jī)程序設(shè)計(jì)言語(yǔ)算法設(shè)計(jì)與分析*河南工程學(xué)院 1.2.1 算法描畫(huà)商定 根本數(shù)據(jù)類(lèi)型: vartype var; 賦值語(yǔ)句： 邏輯運(yùn)算：and, or, not 關(guān)系運(yùn)算, =,=,=,等 數(shù)組描畫(huà)：vartype arraynamen 三種根本的控制構(gòu)造 1.順序構(gòu)造 2.選擇構(gòu)造 3.循環(huán)構(gòu)造 動(dòng)態(tài)空間懇求函數(shù) malloc(size) 模塊描畫(huà) 其他細(xì)節(jié)闡明 算法設(shè)計(jì)與分析*河南工程學(xué)院 1.2.1 一個(gè)簡(jiǎn)單問(wèn)題的求解過(guò)

4、程 1. 問(wèn)題分析：對(duì)問(wèn)題進(jìn)展準(zhǔn)確的了解和描 述從而確認(rèn)問(wèn)題以及問(wèn)題的根本運(yùn)算，并明確求解問(wèn)題 2. 算法分析：根據(jù)確定的問(wèn)題，找出問(wèn)題的處理方法或數(shù)學(xué)模型，對(duì)處置功能求解，并用算法言語(yǔ)進(jìn)展描畫(huà) 3.算法設(shè)計(jì)：對(duì)確定的算法，選擇數(shù)據(jù)構(gòu)造對(duì)分析得到的算法進(jìn)展設(shè)計(jì) 4.算法實(shí)現(xiàn)：利用程序設(shè)計(jì)和軟件開(kāi)發(fā)方法經(jīng)過(guò)程序編輯、編譯、運(yùn)轉(zhuǎn)于調(diào)試實(shí)現(xiàn)算法，對(duì)問(wèn)題進(jìn)展計(jì)算機(jī)求解。算法設(shè)計(jì)與分析*河南工程學(xué)院1.3 算法分析的根底 1.3.1 算法分析的評(píng)價(jià)體系 算法分析主要分析算法在運(yùn)轉(zhuǎn)時(shí)占用的計(jì)算機(jī)資源是多少，既算法運(yùn)轉(zhuǎn)時(shí)的時(shí)間和空間效率 好的算法在完勝利能的前提先占用空間少且執(zhí)行時(shí)間短算法設(shè)計(jì)與分析*河南工

5、程學(xué)院 對(duì)算法的分析和評(píng)價(jià)，普通應(yīng)思索正確性、可維護(hù)性、時(shí)間效率及占用存儲(chǔ)空間等諸多要素。其中評(píng)價(jià)算法的三條主要規(guī)范是： 1、算法實(shí)現(xiàn)所耗費(fèi)的時(shí)間 2、算法實(shí)現(xiàn)所耗費(fèi)的存儲(chǔ)空間 3、算法應(yīng)易于了解、易于編碼、易于調(diào)試。算法設(shè)計(jì)與分析*河南工程學(xué)院 算法復(fù)雜性 = 算法所需求的計(jì)算機(jī)資源 算法的時(shí)間復(fù)雜性T(n)； 算法的空間復(fù)雜性S(n)。 其中n是問(wèn)題的規(guī)模輸入大小。算法設(shè)計(jì)與分析*河南工程學(xué)院 1.3.2 算法的時(shí)間復(fù)雜度 一、影響算法執(zhí)行時(shí)間的要素 1. 問(wèn)題中數(shù)據(jù)存儲(chǔ)的數(shù)據(jù)構(gòu)造 2.算法中采用的數(shù)學(xué)模型 3.算法設(shè)計(jì)的戰(zhàn)略 4.問(wèn)題規(guī)模 5.實(shí)現(xiàn)算法的程序執(zhí)行言語(yǔ) 6.編譯算法產(chǎn)生的機(jī)

6、器代碼的質(zhì)量 7.計(jì)算機(jī)執(zhí)行指令的速度算法設(shè)計(jì)與分析*河南工程學(xué)院 分析算法的時(shí)間復(fù)雜度常用的兩種方法： 事后測(cè)試(Posterior Test)方法 事前分析(Priori Analysis)方法算法設(shè)計(jì)與分析*河南工程學(xué)院 二、 時(shí)間復(fù)雜度 定義1-1 在問(wèn)題規(guī)模為n的算法中，假設(shè)存在兩個(gè)正常數(shù)C和n0，對(duì)恣意nn0,都有 |g(n)|C|f(n)| 那么記作|g(n)|=O(f(n)。其中，O為數(shù)量級(jí)，即階數(shù)。因此，但說(shuō)一個(gè)算法具有O(g(n)的計(jì)算時(shí)間時(shí)，指的假設(shè)此算法用n值不變的同一類(lèi)數(shù)據(jù)在某臺(tái)機(jī)器上運(yùn)轉(zhuǎn)時(shí)，所用時(shí)間總是小于|f(n)|的常數(shù)倍。所以f(n)是計(jì)算時(shí)間g(n)的一個(gè)上

7、界函數(shù)，g(n)的數(shù)量級(jí)為f(n).算法設(shè)計(jì)與分析*河南工程學(xué)院 定義1-2 算法中根本操作反復(fù)執(zhí)行的次數(shù)是問(wèn)題規(guī)模n的某個(gè)函數(shù)f(n)，算法的時(shí)間度量記作 T(n)=O(f(n) 隨著問(wèn)題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率一樣，稱(chēng)作算法的漸進(jìn)時(shí)間復(fù)雜度，簡(jiǎn)稱(chēng)時(shí)間復(fù)雜度。算法設(shè)計(jì)與分析*河南工程學(xué)院 三、時(shí)間復(fù)雜度估算 假設(shè)在程序中有語(yǔ)句xx+y, 這條語(yǔ)句的時(shí)間總量=該語(yǔ)句執(zhí)行的次數(shù)每執(zhí)行一次該語(yǔ)句所需求的時(shí)間； 例1 for 1to n do for 1j to n do xx+1; 語(yǔ)句的最大頻度為n2,所以其時(shí)間復(fù)雜度可表示為O(n2).算法設(shè)計(jì)與分析*河南工程學(xué)院

8、算法中對(duì)所研討的問(wèn)題最重要的操作作為原操作，已原操作在算法中反復(fù)執(zhí)行的次數(shù)作為算法運(yùn)轉(zhuǎn)時(shí)間的衡量準(zhǔn)那么。 例2 a b c xx+y for 1i to n for 1i to n do xx+y do for 1j to n doxx+y ; 1 n n2 O(1) O(n) O(n2)算法設(shè)計(jì)與分析*河南工程學(xué)院 定理1-1 假設(shè)A(n)=amnm+ +a1n+a0 是一個(gè)m次多項(xiàng)式，那么A(n)=O(nm) 證明：取n0=1,當(dāng)nn0時(shí)有 |A(n)|am|nm+ |am-1|nm-1+|a1|n+|a0| (|am|+ |am-1|1/n+|a0|1/nm)nm (|am|+ |a m

9、-1|+|a0|)nm 選取 C=|am|+|am-1|+|a0| 定理闡明，變量n的階數(shù)為m的多項(xiàng)式與其最高價(jià)nm同階。因此計(jì)算時(shí)間為m階的多項(xiàng)式的算法，其時(shí)間都可用O(nm)來(lái)表示。算法設(shè)計(jì)與分析*河南工程學(xué)院 定義1-3 假設(shè)存在兩個(gè)正常數(shù)C和n0，對(duì)恣意nn0都有 |g(n)| C|f(n)| 那么記為g(n)=(f(n)。定義闡明f(n)是g(n)的下界函數(shù)。 定義1-4 假設(shè)存在正常數(shù)C1,C2和n0，對(duì)于一切的nn0，有 C1|f(n)| g(n) C2|f(n)| 那么記為g(n)=(f(n).算法設(shè)計(jì)與分析*河南工程學(xué)院 一個(gè)算法g(n)=(f(n)闡明該算法在最好和最壞情況

10、下的計(jì)算時(shí)間就某一常數(shù)而言是一樣的。算法設(shè)計(jì)與分析*河南工程學(xué)院 比較兩個(gè)函數(shù)的階數(shù)的方法 假設(shè) lim f(n)/g(n)=L 有是以下三種情況 1. 假設(shè)L=a, a 是有限正常數(shù)，那么g(n)=(f(n). 2. 假設(shè)L=0，那么f(n)的階數(shù)比g(n)底 3. 假設(shè)L= ，那么f(n)的階數(shù)比g(n)高算法設(shè)計(jì)與分析*河南工程學(xué)院算法分析中常見(jiàn)的復(fù)雜性函數(shù)算法分析中常見(jiàn)的復(fù)雜性函數(shù)算法設(shè)計(jì)與分析*河南工程學(xué)院小規(guī)模數(shù)據(jù)小規(guī)模數(shù)據(jù)算法設(shè)計(jì)與分析*河南工程學(xué)院中等規(guī)模數(shù)據(jù)中等規(guī)模數(shù)據(jù)算法設(shè)計(jì)與分析*河南工程學(xué)院 四、時(shí)間復(fù)雜度的最好情況和最壞情況算法設(shè)計(jì)與分析*河南工程學(xué)院 1.3.3 算

11、法的空間復(fù)雜度 算法的空間復(fù)雜度是指算法在執(zhí)行過(guò)程中所占輔助存儲(chǔ)空間的大小，用S(n)表示。算法的空間復(fù)雜度S(n)可表示為 S(n)=O(f(n)算法設(shè)計(jì)與分析*河南工程學(xué)院 1.3.4 NP-完全問(wèn)題 可在多項(xiàng)式時(shí)間內(nèi)用確定求精的斷定問(wèn)題的集合稱(chēng)為P類(lèi)問(wèn)題。而一切在多項(xiàng)式時(shí)間內(nèi)用不確定算法求解的判別問(wèn)題的集合稱(chēng)為NP-問(wèn)題算法設(shè)計(jì)與分析*河南工程學(xué)院 確定算法是不確定算法的一種特例，任何一個(gè)P類(lèi)問(wèn)題都屬于NP類(lèi)問(wèn)題算法設(shè)計(jì)與分析*河南工程學(xué)院1.4 根本數(shù)據(jù)構(gòu)造 1.4.1 棧和隊(duì)列 順序棧的數(shù)據(jù)構(gòu)造 typedef struct 1 SElemType *base; 2 SElemTyp

12、e *top; 3 int stacksize; 4 sqStack.算法設(shè)計(jì)與分析*河南工程學(xué)院Push (sqStack, &SElmType e)if S.top-S.base=S.stacksize then if S.base=NULL then exit; S.topS.base+S.stacksize; S.stacksizeS.stacksize+stackincrement*S.tope;S.topS.top+1;算法設(shè)計(jì)與分析*河南工程學(xué)院 Pop (sqStack &S, SElmType &e) 1 if S.top=S.base 2 then return ERROR

13、 3 S.topS.top-1; 4 e*S.top 5 return算法設(shè)計(jì)與分析*河南工程學(xué)院 鏈隊(duì)列的數(shù)據(jù)構(gòu)造 typedef struct Qnode 1 QElemType data; 2 struct Qnode *next; 3 Qnode; typedef struct 1 Qnode *front; 2 Qnode *rear; 3 LinkQueue;算法設(shè)計(jì)與分析*河南工程學(xué)院 EnQueue(LinkQueue &Q, QElemType e 1 p(Qnode *) malloc (sizeof(Qnode); 2 if NULL=p 3 then exit(OVER

14、LOW) 4 p.datae 5 p.nextNULL 6 Q.rear.nextp; 7 Q.rearp; 8 return OK;算法設(shè)計(jì)與分析*河南工程學(xué)院 1.4.2 樹(shù) 定義1-5 樹(shù)是由一個(gè)或多個(gè)節(jié)點(diǎn)組成的有限集合T，節(jié)點(diǎn)滿(mǎn)足如下關(guān)系： 1由一個(gè)特定的節(jié)點(diǎn)稱(chēng)為數(shù)的根節(jié)點(diǎn) 2其他節(jié)點(diǎn)被分成m(m=0)個(gè)互不相交的集合T1,T2, ,Tm，其中每個(gè)集合本身又是一顆樹(shù)，被稱(chēng)為根節(jié)點(diǎn)的子樹(shù)。算法設(shè)計(jì)與分析*河南工程學(xué)院 樹(shù)的根本術(shù)語(yǔ) 1. 孩子、雙親、兄弟 2 節(jié)點(diǎn)的度 3 葉節(jié)點(diǎn)、分支節(jié)點(diǎn) 4 節(jié)點(diǎn)的層數(shù) 5 樹(shù)的深度 6 二叉樹(shù)、滿(mǎn)二叉樹(shù)、完全二叉數(shù)算法設(shè)計(jì)與分析*河南工程學(xué)院 1.4

15、.3圖 圖G是由稱(chēng)之為定點(diǎn)(Vertices)V和邊(Edges)E的兩個(gè)集合所組成，記作G=,V是一個(gè)有限非空的定點(diǎn)集合，這些定點(diǎn)通常記為v1,v2, ,v n。E那么是定點(diǎn)對(duì)偶的集合。E中的每一對(duì)偶就是G的一條邊。算法設(shè)計(jì)與分析*河南工程學(xué)院 有向圖：假設(shè)圖中的對(duì)偶是有序的，那么稱(chēng)圖是有向圖，否那么是無(wú)向圖。有向圖用尖括號(hào)來(lái)表示，無(wú)向圖用圓括號(hào)來(lái)表示(v1,v2). 權(quán)：圖的邊或弧有時(shí)與一些數(shù)值相關(guān)，稱(chēng)作權(quán)Weight)，帶權(quán)的圖稱(chēng)為網(wǎng)絡(luò)(Network).算法設(shè)計(jì)與分析*河南工程學(xué)院1.5 迭代法 迭代法是一種不斷用變量的當(dāng)前值推出新值的處理問(wèn)題的方法。利用迭代戰(zhàn)略求解問(wèn)題，分三步進(jìn)展

16、1.確定迭代模型 2.建立迭代關(guān)系式 3.迭代過(guò)程控制算法設(shè)計(jì)與分析*河南工程學(xué)院 1.5.1 遞推法 遞推法是迭代法的最簡(jiǎn)單方式。簡(jiǎn)單的遞推方式，是從小規(guī)模的問(wèn)題推出解出大規(guī)模問(wèn)題的方法，也稱(chēng)為“正推算法設(shè)計(jì)與分析*河南工程學(xué)院 1.5.2 倒推法 倒推法是指對(duì)某些特殊問(wèn)題所采用的違反常規(guī)的，從后向前推解問(wèn)題的方法算法設(shè)計(jì)與分析*河南工程學(xué)院 1.5.3 迭代法解方程 迭代法解方程的本質(zhì)是按照以下步驟構(gòu)造一個(gè)序列x0,x1,x2,xn, 來(lái)逐漸逼近方程f(x)=0的解 1 選取適當(dāng)?shù)某踔祒0； 2 確定迭代格式，即建立迭代關(guān)系，將方程f(x)=0 改寫(xiě)為x=(x)的等價(jià)方式。算法設(shè)計(jì)與分析*

17、河南工程學(xué)院算法設(shè)計(jì)與分析*河南工程學(xué)院1.6 遞歸和消除遞歸 1.6.1 遞歸 遞歸算法中一個(gè)模塊函數(shù)、過(guò)程除了可調(diào)用其他模塊函數(shù)、過(guò)程外，還可以直接或間接地調(diào)用本身。 遞歸是一種比迭代更強(qiáng)、更好的構(gòu)造。它把一個(gè)復(fù)雜的大問(wèn)題層層轉(zhuǎn)化為一個(gè)原問(wèn)題類(lèi)似的簡(jiǎn)單的小問(wèn)題，然后逐漸求解小問(wèn)題，最后經(jīng)過(guò)回溯法得到原問(wèn)題的解。算法設(shè)計(jì)與分析*河南工程學(xué)院 遞歸算法的三步驟1. 分析問(wèn)題、尋覓遞歸 2. 設(shè)置邊境、控制遞歸 3.設(shè)計(jì)函數(shù)、確定參數(shù)算法設(shè)計(jì)與分析*河南工程學(xué)院例例 階乘函數(shù)階乘函數(shù) 階乘函數(shù)可遞歸地定義為：階乘函數(shù)可遞歸地定義為：00)!1(1!nnnnn邊境條件邊境條件遞歸方程遞歸方程邊境條

18、件與遞歸方程是遞歸函數(shù)的二個(gè)要素，遞歸函數(shù)只需具備了這兩個(gè)要素，才干在有限次計(jì)算后得出結(jié)果。算法設(shè)計(jì)與分析*河南工程學(xué)院例例 Fibonacci Fibonacci數(shù)列數(shù)列無(wú)窮數(shù)列無(wú)窮數(shù)列1 1，1 1，2 2，3 3，5 5，8 8，1313，2121，3434，5555，稱(chēng)為，稱(chēng)為FibonacciFibonacci數(shù)列。它可以遞歸地定義為：數(shù)列。它可以遞歸地定義為：邊境條件邊境條件遞歸方程遞歸方程110)2() 1(11)(nnnnFnFnF第n個(gè)Fibonacci數(shù)可遞歸地計(jì)算如下：int fibonacci(int n) if (n 0 2 then Hanoi(n-1,a,c,b); 3 print(“Move disc, n. “from pile, a, “to b); 4 hanoi(n-1,c,b,a)算法設(shè)計(jì)與分析*河南工程學(xué)院優(yōu)點(diǎn)：構(gòu)造明晰，可讀性強(qiáng)，而且容易用優(yōu)點(diǎn)：構(gòu)造明晰，可讀性強(qiáng)，而且容易用數(shù)學(xué)歸納法來(lái)證明算法的正確