[學(xué)習(xí)]算法設(shè)計(jì)與分析王佳01概述

1、主講教師 王佳james.wong@foxmail.com15902799068信息學(xué)院,,算法設(shè)計(jì)與分析,課程前言,一、什么是算法,事情太多了，怎么才能讓計(jì)算機(jī)幫我做呢？,實(shí)際問(wèn)題,程序,數(shù)學(xué)模型,,算法,,,算法是指解題方案準(zhǔn)確而完整的描述,2/90,實(shí)際問(wèn)題：超級(jí)女聲收入到底有多少,程序:Main(){…...},數(shù)學(xué)模型：總收入=短信收入+廣告收入,,算法：收入( 今天 ) { if (比賽日程沒(méi)結(jié)束)

2、{ 短信收入 = 今天短信數(shù) * 短信單價(jià); if (今天有比賽) 廣告收入 = 廣告單價(jià) * 廣告時(shí)長(zhǎng); } else return 收入 = 短信收入 + 廣告收入;}總收入( ){ for( i = 開始日期; i <= 最后一天; i++ ) 總收入 += 收入( i ); return 總收入；},,,3/90,舉個(gè)例子：排序

3、問(wèn)題描述：將一組數(shù)按從小到大的順序整理有序基本思想：小的數(shù)往前排，大的數(shù)往后排怎么排？算法冒泡排序選擇排序歸并排序快速排序堆排序Shell排序…,,每種算法都是一組特定的規(guī)則，規(guī)定了一種處理數(shù)據(jù)的運(yùn)算方法,課程前言,4/90,問(wèn)題：既然每種方法都可以實(shí)現(xiàn)排序之目的，何必費(fèi)心研究這么多排序算法？其一：“瞎想”，就像玩智力游戲，人們樂(lè)衷于尋找不同的方法解決各種各樣的問(wèn)題。其二：研究的需要，算法和算法間是有區(qū)別的，我們

4、有必要去研究，去分析。性質(zhì)不同：穩(wěn)定、不穩(wěn)定性能不同：速度、空間適用場(chǎng)合不同其三，應(yīng)用的需求，問(wèn)題有千百萬(wàn)種，沒(méi)有萬(wàn)能的算法適合所有的應(yīng)用。需要我們找出算法的設(shè)計(jì)規(guī)律，并設(shè)計(jì)出解決問(wèn)題的新算法怎么選擇：根據(jù)性能、結(jié)合需求、綜合選擇如何了解每種算法的性能？算法的分析,5/90,二、算法分析了解算法的性能：算法速度：快還是慢？如何衡量？怎么比較？空間使用：大還是??？如何衡量？怎么比較？其它方面的性質(zhì)等。,,課程前言,6

5、/90,三、為什么要學(xué)習(xí)算法1. 編程需要任何程序都需要算法(the core of computer science)憑借一句話獲得圖靈獎(jiǎng)的Pascal之父——瑞士計(jì)算機(jī)科學(xué)家尼古拉斯·沃斯Nicklaus Wirth程序=數(shù)據(jù)結(jié)構(gòu)+算法 (Algorithm+Data Structures=Programs)算法是計(jì)算機(jī)科學(xué)的基礎(chǔ)，更是程序的基石，只有具有良好的算法基礎(chǔ)才能成為訓(xùn)練有素的軟件人才,課程前言,

6、7/90,2. 改造世界的需要世界上還有很多很多的問(wèn)題等待你解決，有無(wú)數(shù)的程序等待你去編。3. 國(guó)家綜合實(shí)力的體現(xiàn)（大）從軟實(shí)力的角度，算法是國(guó)家科技生產(chǎn)力的核心。是國(guó)家綜合實(shí)力的體現(xiàn)。,8/90,四、頭疼 問(wèn)題太多，算法太多了，學(xué)不過(guò)來(lái)是的，都學(xué)過(guò)來(lái)是不可能的。甚至專一門已經(jīng)很了不起。學(xué)習(xí)算法設(shè)計(jì)與分析的策略、技術(shù)和方法，把握解決問(wèn)題的規(guī)律，為設(shè)計(jì)更復(fù)雜、更有效的算法奠定基礎(chǔ)。需要同學(xué)們不斷學(xué)習(xí)，

7、深入思考，創(chuàng)新設(shè)計(jì)。,課程前言,9/90,五、學(xué)習(xí)過(guò)程：痛苦并快樂(lè)著1.枯燥的過(guò)程繁vs煩：學(xué)習(xí)一個(gè)算法如同做一道數(shù)學(xué)題，熟能生巧2.智慧的積累方法的掌握、技術(shù)的升華3.理論的貢獻(xiàn)算法成就或在于理論的貢獻(xiàn)，而不僅僅是技術(shù)的提高。如何成就好算法：好思想+好技術(shù),課程前言,10/90,六、好算法從理論的角度說(shuō)，好算法應(yīng)該有較低的時(shí)間復(fù)雜度（高速）和空間復(fù)雜度（低耗），但好的算法還要依靠好的算法實(shí)現(xiàn)，需要理論與技術(shù)、技巧的

8、結(jié)合才能最終實(shí)現(xiàn)好的算法。從應(yīng)用的角度說(shuō)，能有效地解決問(wèn)題的算法都是好算法——不管黑貓白貓，抓住老鼠就是好貓；不管A算法、B算法，能解決問(wèn)題就是好算法。,課程前言,11/90,概述,課程名稱：算法設(shè)計(jì)與分析 Design and Analysis of Algorithms 先修課程C/C++語(yǔ)言程序設(shè)計(jì)，數(shù)據(jù)結(jié)構(gòu)課程核心 介紹算法設(shè)計(jì)與分析的基本理論、方法和技術(shù)， 奠定算法設(shè)計(jì)的基礎(chǔ)教材 十一五國(guó)

9、家級(jí)規(guī)劃教材，《算法設(shè)計(jì)與分析》陳慧南編著，電子工業(yè)出版社,12/90,主要參考書計(jì)算機(jī)算法基礎(chǔ)， 余祥宣等編著， 華中科技大學(xué)出版社Introduction to algorithms, Thomas H. Cormen,etc., second edition, The MIT Press.Algorithm Design，Michael T. Goodrich算法設(shè)計(jì)與分析，王曉東，清華大學(xué)出版社,13/90,其它

10、參考書The Art of Computer Programming, Donald E.Knuth. Volume 1-3, Second Edition. Data Structures, Algorithms, and Applications in C++(Part 3) Sartaj Sahni, China Machine Pressetc.,14/90,1.1 算法的定義及特性,1. 什么是算法？算法如數(shù)字、計(jì)算

11、一樣，是一個(gè)基本概念。算法是解一確定類問(wèn)題的任意一種特殊的方法。在計(jì)算機(jī)科學(xué)中，算法是使用計(jì)算機(jī)解一類問(wèn)題的精確、有效方法的代名詞； 算法是一組有窮的規(guī)則，它規(guī)定了解決某一特定類型問(wèn)題的一系列運(yùn)算。,15/90,對(duì)算法概念的理解算法由運(yùn)算組成 算術(shù)運(yùn)算、邏輯運(yùn)算、賦值運(yùn)算、過(guò)程調(diào)用算法有其特殊性 解決不同問(wèn)題的算法是不相同的，有沒(méi)有一個(gè)萬(wàn)能的算法？算法是有窮的計(jì)算過(guò)程 靜態(tài)上：規(guī)則/運(yùn)算/語(yǔ)句的

12、數(shù)量有窮 動(dòng)態(tài)上：計(jì)算過(guò)程/計(jì)算時(shí)間有限,16/90,我們已經(jīng)接觸過(guò)的算法： 排序算法：將已知的n個(gè)元素按照關(guān)鍵值大小的非增/非降順序重新排列。 如：冒泡排序、插入排序、歸并排序 查找算法：從已知的元素集合中找出滿足要求的一個(gè)或一組元素。 如：順序查找、二分查找 圖算法：在已知的圖中找出滿足某些性質(zhì)的結(jié)點(diǎn)或邊。 如：最短路徑算法、最小成本生成樹,17/90,思考：,我們學(xué)會(huì)了解決一個(gè)個(gè)具體問(wèn)題的

13、算法，那么在這些算法的設(shè)計(jì)中有沒(méi)有一些共性的東西？有沒(méi)有可以總結(jié)出來(lái)的規(guī)律、規(guī)則和方法？這些規(guī)律、規(guī)則和方法對(duì)于其它算法的設(shè)計(jì)有沒(méi)有指導(dǎo)意義？能不能找到一些算法設(shè)計(jì)的一般策略、技術(shù)和方法？,18/90,2. 算法的五個(gè)重要特性,輸入、輸出、確定性、能行性、有窮性,1）輸入 每個(gè)算法都有0個(gè)或多個(gè)輸入。這些輸入是在算法開始之前給出的量，取自于特定的對(duì)象集合——定義域2）輸出 一個(gè)算法產(chǎn)生一個(gè)或多個(gè)輸出，這

14、些輸出是同輸入有某種特定關(guān)系的量。,19/90,3）確定性：算法使用的每種運(yùn)算必須要有確切的定義，不能有二義性。 例：不符合確定性的運(yùn)算23/0 計(jì)算5+3或計(jì)算7-3未賦值變量參與運(yùn)算,如果a == 6那么x該取什么值呢？,再如： if (a%2 == 0) x = 1; if (a%3 == 0) x = 0;,20/90,4）能行性算法的

15、每一條指令必須足夠基本，它們可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來(lái)實(shí)現(xiàn)。能行性包含兩層意思：1.算法中每一步必須能夠?qū)崿F(xiàn)(滿足計(jì)算機(jī)的實(shí)際運(yùn)算條件)2.結(jié)果應(yīng)能達(dá)到預(yù)期目的,21/90,如何認(rèn)識(shí)算法的確定性和能行性？,確定性和能行性是算法設(shè)計(jì)過(guò)程可能存在的問(wèn)題。一個(gè)實(shí)際的程序設(shè)計(jì)語(yǔ)言定義了該語(yǔ)言中可以使用的數(shù)據(jù)類型和能夠參與的運(yùn)算，編譯器可以對(duì)程序中的非法運(yùn)算檢錯(cuò)。非確定、非能行的的“臆造”運(yùn)算是不能存在的，程序的正確性主要

16、在于邏輯正確。但算法本身的正確性不僅在于此。,22/90,5）有窮性 一個(gè)算法總是在執(zhí)行了有窮步的運(yùn)算之后終止。,計(jì)算過(guò)程：滿足確定性、能行性、輸入、輸出，但不一定滿足有窮性的一組規(guī)則。 算法和計(jì)算過(guò)程的關(guān)系： 計(jì)算過(guò)程：操作系統(tǒng)(不終止的運(yùn)行過(guò)程) 算法是“可以終止的計(jì)算過(guò)程”,23/90,時(shí)效性：實(shí)際問(wèn)題往往都有時(shí)間要求。例：國(guó)際象棋（啟發(fā)） 數(shù)值天氣預(yù)報(bào) 只有在要求的時(shí)間內(nèi)

17、解決問(wèn)題才是有意義的。,24/90,1.2 問(wèn)題和問(wèn)題求解,問(wèn)題求解（problem solving）是尋找一種方法來(lái)實(shí)現(xiàn)目標(biāo)。問(wèn)題求解過(guò)程（problem solving process）是人們通過(guò)使用問(wèn)題領(lǐng)域知識(shí)來(lái)理解和定義問(wèn)題，并憑借自身的經(jīng)驗(yàn)和知識(shí)去選擇和使用適當(dāng)?shù)膯?wèn)題求解策略、技術(shù)和工具，將一個(gè)問(wèn)題描述轉(zhuǎn)換成問(wèn)題解的過(guò)程。計(jì)算機(jī)求解問(wèn)題的關(guān)鍵之一是尋找一種問(wèn)題求解策略（problem solving strategy），

18、得到求解問(wèn)題的算法，從而得到問(wèn)題的解。,25/90,問(wèn)題求解過(guò)程,理解問(wèn)題（understand the problem） 設(shè)計(jì)方案（devise a plan） 實(shí)現(xiàn)方案（carry out the plan） 回顧復(fù)查（look back）,26/90,算法問(wèn)題求解過(guò)程,算法分類一個(gè)精確算法（exact algorithm）總能保證求得問(wèn)題的解。一個(gè)啟發(fā)式算法（heuristic algorithm）通過(guò)使用某種規(guī)則、簡(jiǎn)化

19、或智能猜測(cè)來(lái)減少問(wèn)題求解時(shí)間。,27/90,對(duì)于最優(yōu)化問(wèn)題，一個(gè)算法如果致力于尋找近似解而不是最優(yōu)解，被稱為近似算法（approximation algorithm）。 如果在算法中需做出某些隨機(jī)選擇，隨機(jī)算法（randomized algorithm）。,28/90,與算法學(xué)習(xí)相關(guān)的內(nèi)容,五個(gè)方面：設(shè)計(jì)、表示、證明、分析、測(cè)試,1）設(shè)計(jì)：構(gòu)思算法的處理規(guī)則，創(chuàng)造性的活動(dòng)。2）表示：用語(yǔ)言把算法描述出來(lái)。自然語(yǔ)言 流程圖

20、 偽代碼 程序設(shè)計(jì)語(yǔ)言,29/90,與算法學(xué)習(xí)相關(guān)的內(nèi)容,3）證明：證明算法的正確性。證明算法對(duì)所有輸入都停止證明對(duì)每個(gè)輸入都產(chǎn)生正確結(jié)果調(diào)試程序?程序正確性證明程序調(diào)試只能證明程序有錯(cuò)，不能證明程序無(wú)錯(cuò)誤!,30/90,4）分析：對(duì)算法的時(shí)、空特性做定性、定量分析，以了解算法的性質(zhì)。5）測(cè)試：將算法變成程序，放到計(jì)算機(jī)上運(yùn)行，觀察運(yùn)行情況,編程中的調(diào)試：排錯(cuò)過(guò)程。“調(diào)試只能指出有錯(cuò)誤，而不能指出它們不存在錯(cuò)誤”

21、運(yùn)行中的測(cè)試：分析過(guò)程。驗(yàn)證分析結(jié)論，進(jìn)一步優(yōu)化算法設(shè)計(jì)。本課程集中于學(xué)習(xí)算法的設(shè)計(jì)與分析。通過(guò)學(xué)習(xí)，掌握計(jì)算機(jī)算法設(shè)計(jì)和分析基本策略與方法，為設(shè)計(jì)更復(fù)雜、更有效的算法奠定基礎(chǔ),31/90,1.3 分析算法基礎(chǔ),從一個(gè)例子開始講起：插入算法插入分類算法描述：輸入：n個(gè)元素存放在數(shù)組A中：A[0]~A[n-1]，無(wú)序輸出：按照從小到大的順序重新整理有序的數(shù)組A[1]~A[n]設(shè)計(jì)思路： 1. 將第一個(gè)元素（A[0]）

22、看作只有一個(gè)元素的有序子序列； 2. 置循環(huán) i=1 to n-1，將A[i]插入到由A[0]~A[i-1]元素組成的有序子序列。思考問(wèn)題： 上述設(shè)計(jì)思路對(duì)嗎？如何實(shí)現(xiàn)？,32/90,算法描述： procedure INSERTIONSORT(A,n) A(0)←-∞ //A[0]做監(jiān)視哨

23、 for i←2 to n do //從第二個(gè)元素開始循環(huán) item←A(i); //將A[i]放到臨時(shí)變量item中 j←i-1 //從后往前查找當(dāng)前元素的插入位置 while i

24、tem<A(j) do A(j+1)←A(j); //比item大的元素往后移一位 j←j-1; //繼續(xù)往前查找 repeat A(j+1) ←item; //將item

25、插入到正確的位置上 repeat end INSERTIONSORT,33/90,基于上述算法，思考：這個(gè)算法描述正確嗎？能行、確定、輸入、輸出、有窮？ 正確性證明運(yùn)算得快嗎？ 時(shí)間復(fù)雜度分析使用了多少內(nèi)存？ 空間復(fù)雜度分析進(jìn)一步我們需要回答：它能夠應(yīng)用到那些領(lǐng)域？

26、 要做深入進(jìn)一步分析 利用不同語(yǔ)言實(shí)現(xiàn)需要那些技巧? 實(shí)現(xiàn),34/90,1. 分析算法的目的,算法選擇的需要：對(duì)同一個(gè)問(wèn)題可以設(shè)計(jì)不同的算法，不同的算法對(duì)時(shí)間和空間需求是不同的算法優(yōu)化的需要：有沒(méi)有可以改進(jìn)的地方，以使算法工作的更好？分析算法的目的在于：通過(guò)對(duì)算法的分析了解算法的性能1）可以在解決同一問(wèn)題的不同算法之間比較性能的好壞，從而運(yùn)行好的算法，改進(jìn)差的算法，避免無(wú)益的人力

27、和物力浪費(fèi)。2）可以對(duì)算法的性質(zhì)作深入了解，從而可以進(jìn)一步優(yōu)化算法，讓其更好地工作。,35/90,2. 計(jì)算的約定,算法的執(zhí)行時(shí)間是算法中所有運(yùn)算執(zhí)行時(shí)間的總和，可以表示為: 算法的執(zhí)行時(shí)間= 其中， fi ：是運(yùn)算i的執(zhí)行次數(shù)，稱為該運(yùn)算的頻率計(jì)數(shù)僅與算法的控制流程有關(guān)，與實(shí)際使用的計(jì)算機(jī)硬件和編制程序的語(yǔ)言無(wú)關(guān)。 ti ：是運(yùn)算i在實(shí)際的計(jì)算機(jī)上每執(zhí)行一

28、次所用的時(shí)間 與程序設(shè)計(jì)語(yǔ)言和計(jì)算機(jī)硬件有關(guān)。 如何確定算法使用了哪些運(yùn)算,每種運(yùn)算的fi和ti又是多少?,36/90,運(yùn)算的分類,依照運(yùn)算的時(shí)間特性，將運(yùn)算分為時(shí)間囿界于常數(shù)的運(yùn)算和時(shí)間非囿界于常數(shù)的運(yùn)算。囿界：限于......時(shí)間囿界于常數(shù)的運(yùn)算： 基本算術(shù)運(yùn)算，如整數(shù)、浮點(diǎn)數(shù)的加、減、乘、除 字符運(yùn)算、賦值運(yùn)算、過(guò)程調(diào)用等 特點(diǎn)：盡管每種運(yùn)算執(zhí)行時(shí)間不同，但一般只花一個(gè)固定量的時(shí)間（單位時(shí)間）就可

29、完成。 例： 1+1 = 2 vs 10000+10000 = 20000 100*100 = 10000 vs 10000*10000 = 100000000 CALL INSERTIONSORT,37/90,更一般的情況,設(shè)有n種運(yùn)算c1，c2，…，cn，它們的執(zhí)行時(shí)間分別是t1，t2，…，tn。令t0=max(t1，t2，…，tn)，則每

30、種運(yùn)算執(zhí)行一次的時(shí)間都可以用t0進(jìn)行限界(上界)。視t0為一個(gè)單位時(shí)間，則這些運(yùn)算“理論”上都可視為僅花一個(gè)固定的單位時(shí)間t0即可完成的運(yùn)算稱具有這種性質(zhì)的運(yùn)算為時(shí)間囿界于常數(shù)的運(yùn)算。,38/90,運(yùn)算的分類,時(shí)間非囿界于常數(shù)的運(yùn)算：字符串操作：與字符串中字符的數(shù)量成正比例：字符串的比較運(yùn)算（strcmp）記錄操作：與記錄的屬性數(shù)、屬性類型等有關(guān)特點(diǎn)：運(yùn)算時(shí)間與操作數(shù)相關(guān)，每次執(zhí)行的時(shí)間是一個(gè)不定的量。,39/90,怎么

31、分析時(shí)間非囿界于常數(shù)的運(yùn)算？這類運(yùn)算通常是由更基本的運(yùn)算組成的。而這些基本運(yùn)算是時(shí)間囿界于常數(shù)的運(yùn)算。如：字符串的比較運(yùn)算是由一組字符比較運(yùn)算組成的。非囿界于常數(shù)的運(yùn)算的一次執(zhí)行時(shí)間是其包含的所有基本運(yùn)算的執(zhí)行時(shí)間之和： 如：字符串比較時(shí)間tstring tstring = Length（String）* tchar故：分析時(shí)間非囿界于常數(shù)的運(yùn)算時(shí)

32、，將其分解成若干時(shí)間囿界于常數(shù)的運(yùn)算即可。,40/90,3. 工作數(shù)據(jù)集的選擇,算法的執(zhí)行情況與輸入數(shù)據(jù)的特征有關(guān)，體現(xiàn)在：算法的執(zhí)行時(shí)間與輸入數(shù)據(jù)的規(guī)模相關(guān)，一般規(guī)模越大,執(zhí)行時(shí)間越長(zhǎng)。在不同的數(shù)據(jù)配置上，同一算法有不同的執(zhí)行情況，可分為最好、最壞和平均等情況討論。編制不同的數(shù)據(jù)配置，分析算法的最好、最壞、平均工作情況是算法分析的一項(xiàng)重要工作。如插入排序的最好（O(n)）、最壞(O((n2))工作情況。,41/90,注：

33、編制測(cè)試數(shù)據(jù)對(duì)算法分析與程序調(diào)試都是關(guān)鍵的，但目的不同。算法分析數(shù)據(jù)集：反映算法的典型執(zhí)行情況（最好、最壞、平均）調(diào)試程序數(shù)據(jù)集：排錯(cuò)。力求走到程序的每個(gè)分支，驗(yàn)證各種情況下程序執(zhí)行的正確性。,42/90,4. 如何進(jìn)行算法分析？,對(duì)算法的全面分析將分兩個(gè)階段進(jìn)行：事前分析和事后測(cè)試（理論分析和程序測(cè)試）。事前分析：求算法時(shí)間/空間復(fù)雜度的限界函數(shù)。限界函數(shù)通常是關(guān)于問(wèn)題規(guī)模n的特征函數(shù)，被表示成Ο、Ω或Θ的形式。 如歸并排序

34、的O(nlogn)。特征函數(shù)是通過(guò)分析算法的控制邏輯得來(lái)的，是對(duì)算法所用運(yùn)算執(zhí)行次數(shù)的統(tǒng)計(jì)結(jié)果。與使用的程序設(shè)計(jì)語(yǔ)言和計(jì)算機(jī)硬件無(wú)關(guān)。,43/90,事后測(cè)試：將算法編制成程序，放到實(shí)際的計(jì)算機(jī)上運(yùn)行，收集程序的執(zhí)行時(shí)間和空間占用等統(tǒng)計(jì)資料，然后進(jìn)行分析判斷。事后測(cè)試與物理實(shí)現(xiàn)直接有關(guān)。算法分析主要集中于與物理實(shí)現(xiàn)無(wú)關(guān)的事前分析階段——獲取算法的理論時(shí)間/空間復(fù)雜度。,44/90,1）事前分析,目標(biāo)：獲取算法的時(shí)間（空間）復(fù)雜度函

35、數(shù)，從理論上分析算法性能的好壞?？梢苑譃闀r(shí)間、空間兩個(gè)方面： 時(shí)間分析：了解算法中使用了哪些運(yùn)算（具有單位執(zhí)行時(shí)間）。分析程序的控制流程，從而確定各類運(yùn)算的執(zhí)行次數(shù)。一般情況下，執(zhí)行次數(shù)越多，程序的執(zhí)行時(shí)間越長(zhǎng)。將對(duì)運(yùn)算執(zhí)行次數(shù)的分析結(jié)果表示成關(guān)于問(wèn)題規(guī)模n的特征函數(shù)。算法性能有最好、平均、最壞等情況，與數(shù)據(jù)配置有關(guān)。分析典型的數(shù)據(jù)配置，了解算法在各種情況下的執(zhí)行情況。,45/90,空間分析：分析算法中各類變量的定義

36、情況分析算法的嵌套結(jié)構(gòu)中變量的使用情況將空間占用量表示成為問(wèn)題規(guī)模n的特征函數(shù)?？臻g占用有最大、平均、最少等情況，與數(shù)據(jù)配置有關(guān)。分析典型的數(shù)據(jù)配置，了解算法在各種情況下的空間占用情況。,46/90,如何進(jìn)行時(shí)間分析？,統(tǒng)計(jì)算法中各類運(yùn)算的執(zhí)行次數(shù)—頻率計(jì)數(shù) ★ 統(tǒng)計(jì)對(duì)象：運(yùn)算 1）基本運(yùn)算：時(shí)間囿界于常數(shù)的運(yùn)算 2）復(fù)合運(yùn)算：具有固定執(zhí)行時(shí)間的程序塊，如一條語(yǔ)句、一個(gè)過(guò)程或函數(shù)等 ★

37、頻率計(jì)數(shù)：算法中語(yǔ)句或運(yùn)算的執(zhí)行次數(shù)，從算法的控制流程得來(lái)。 順序結(jié)構(gòu)中的運(yùn)算/語(yǔ)句：執(zhí)行次數(shù)計(jì)為1 嵌套結(jié)構(gòu)中的運(yùn)算/語(yǔ)句：執(zhí)行次數(shù)等于循環(huán)執(zhí)行的次數(shù) ★ 控制流程分析的關(guān)鍵：確定算法中使用的嵌套結(jié)構(gòu)，包括循環(huán)語(yǔ)句、嵌套調(diào)用等。,47/90,例：執(zhí)行次數(shù)的統(tǒng)計(jì) x←x+y for i ←1 to n do for i ←1 to n do

38、 x ← x + y for j ←1 to n do repeat x ← x +y repeat

39、 repeat (a) (b) (c) 分析： (a)： x←x+y執(zhí)行了1次 (b)： x←x+y執(zhí)行了n次 (c)： x←x+y執(zhí)行了n2次,48/90,★ 頻率計(jì)數(shù)通常是問(wèn)題規(guī)模n的函數(shù)：n0,n,n2,… ★ 算法的執(zhí)行時(shí)間是算法中各類運(yùn)算執(zhí)行

40、時(shí)間之和，正比于各類運(yùn)算的頻率計(jì)數(shù)之和。,49/90,例：插入排序 procedure INSERTIONSORT(A,n) //將A(1：n)中的元素按非降次序分類，n≥1// 執(zhí)行次數(shù) 單位執(zhí)行時(shí)間 A(0)←-∞//設(shè)置初始邊界值 1 t1 for j←2 to n do //A(1:

41、j-1)已分類// n-1 t2 item←A(j); n-1 t3 i←j-1

42、 n-1 t4 while item<A(i) do //0≤i<j// 最多i次,最少1次 t5 A(i+1)←A(i); 最多i-1次,最少0次 t6

43、i←i-1; 最多i-1次,最少0次 t4 repeat A(i+1) ←item; n-1次 t7 repeat end INSERTIONSORT 最壞情況時(shí)間：,50/90

44、,令 t0=max(t1,t2,t3,t4,t5,t6,t7)，則,最壞情況,最好情況,51/90,★ 事前分析的結(jié)果與所使用的機(jī)器及其他環(huán)境因素?zé)o關(guān)（如程序設(shè)計(jì)語(yǔ)言、編譯器），只與算法本身的控制流程有關(guān)。 ★ 對(duì)算法最主要的部分進(jìn)行分析,抓住主要矛盾，如插入排序中,可以僅集中于對(duì)for/while雙重嵌套循環(huán)的分析，而忽略順序或執(zhí)行次數(shù)低的部分。,52/90,函數(shù)表達(dá)式的數(shù)量級(jí)（階） 函數(shù)表達(dá)式中的最高次項(xiàng)的次數(shù)，是衡量頻

45、率計(jì)數(shù)的“大小”的一種測(cè)度。 數(shù)量級(jí)從本質(zhì)上反映了算法復(fù)雜度的高低數(shù)量級(jí)越小，算法的復(fù)雜度越低，同等規(guī)模下算法執(zhí)行時(shí)間越短。反之，數(shù)量級(jí)越大，算法的復(fù)雜度越高，同等規(guī)模下算法執(zhí)行時(shí)間越長(zhǎng)。 例：假如求解同一個(gè)問(wèn)題的三個(gè)算法分別具有n， n2 ， n3數(shù)量級(jí)。若n=10，則可能的執(zhí)行時(shí)間將分別是10，100，1000個(gè)單位時(shí)間。,53/90,限界函數(shù)：用頻率計(jì)數(shù)函數(shù)表達(dá)式中的最高次項(xiàng)

46、表示限界函數(shù)記為： g(n)。 g(n)通常是關(guān)于n的形式簡(jiǎn)單的函數(shù)式，如：logn，nlogn，n2等 ★ 不同算法的g(n)有不同的具體形式?！?g(n)通常是對(duì)算法中最復(fù)雜的計(jì)算部分分析而來(lái)的。 ★ g(n)忽略了函數(shù)表達(dá)式中次數(shù)較低的“次要”項(xiàng)，體現(xiàn)了算法復(fù)雜性的最本質(zhì)特征?！?g(n)通常取單項(xiàng)的形式。空間特性分析（與時(shí)間特性的分析類似，略）,54/90,2）事后測(cè)試,把

47、算法編制成程序，在實(shí)際的計(jì)算機(jī)硬件平臺(tái)上運(yùn)行程序，統(tǒng)計(jì)執(zhí)行中實(shí)際耗費(fèi)的準(zhǔn)確的時(shí)間與空間，與事前分析的結(jié)論進(jìn)行比較，驗(yàn)證先前的分析結(jié)論——包括正確性、執(zhí)行性能等，比較、優(yōu)化所設(shè)計(jì)的算法。,55/90,5. 計(jì)算時(shí)間的漸近表示,算法時(shí)間/空間復(fù)雜度的限界函數(shù)常用的有三個(gè)：上界函數(shù)、下界函數(shù)、“均值”函數(shù)。定義如下：記：算法的實(shí)際計(jì)算時(shí)間為f(n)，計(jì)算時(shí)間的限界函數(shù)為g(n)，其中，n是問(wèn)題規(guī)模的某種測(cè)度。f(n)是與機(jī)器及語(yǔ)言有關(guān)的

48、量。g(n)是事前分析的結(jié)果，一個(gè)形式簡(jiǎn)單的函數(shù)，與頻率計(jì)數(shù)有關(guān)、而與機(jī)器及語(yǔ)言無(wú)關(guān)。,56/90,1）O、Ω、Θ記號(hào),定義1. 1（上界函數(shù)）如果存在兩個(gè)正常數(shù)c和n0，對(duì)于所有的n≥n0，有|f(n)| ≤ c|g(n)|，則記作f(n) = Ο(g(n))。 含義：如果算法用n值不變的同一類數(shù)據(jù)（規(guī)模相等，性質(zhì)相同）在某臺(tái)機(jī)器上運(yùn)行，所用的時(shí)間總小于|g(n)|的一個(gè)常數(shù)倍。函數(shù)f 至多是函數(shù)g 的c倍

49、，除非n<n0。即是說(shuō)，當(dāng)n 充分大時(shí)，g 是f 的一個(gè)上界函數(shù)（在相差一個(gè)非零常數(shù)倍的情況下）。f(n)的數(shù)量級(jí)就是g(n)。,57/90,g(n)是通過(guò)對(duì)算法中運(yùn)算使用情況的分析，得出的函數(shù)表達(dá)式，通常情況下，取函數(shù)式里的最高次項(xiàng)，舍掉低階項(xiàng)和常數(shù)（因?yàn)榈碗A項(xiàng)和常數(shù)最終被湮滅在高次項(xiàng)里），且忽略系數(shù)。如：c=O(1): f(n)等于非零常數(shù)，可看作n04n+3=O(n): 可取c＝5，n0＝3100n+6=O(n)

50、: 可取 c=101，n0＝66×2n+n2=O(2n): 可取c =7，n0=4 10n2+4n+3=O(n2)3log n + 2n + n2 =O(n2)nlog n +n2=O(n2),58/90,注：1．總是試圖求出數(shù)量級(jí)最小的g(n)作為f(n)的上界函數(shù)，即， g(n)應(yīng)該盡量接近函數(shù)f(n)。如若：3n+2=O(n2) 則是松散的界限；而：3n+2=O(n) 就是較好的界限。數(shù)量級(jí)越小，

51、限界越精確。2．不要產(chǎn)生錯(cuò)誤界限。如，n2+100n+6，當(dāng)nc-100 就有 n2+100n+6>c×n。提示：注意大系數(shù)低次項(xiàng)的影響同理，3n2+4×2n=O(n)也是錯(cuò)誤的。,59/90,3． f(n)=O(g(n))不能寫成g(n)=O(f(n))。 f(n)與g(n)并不等價(jià)，這里的等號(hào)也并不是通常相等的含義。 O更精確的定義可

52、以用集合表示： O(g(n))={f(n)|f(n)滿足：存在正的常數(shù)c 和n0，使得當(dāng)n ≥ n0 時(shí)，f(n) ≤ cg(n)} 這里O(g(n))是一個(gè)集合，f(n)=O(g(n))讀作： “f(n)是g(n)的一個(gè)大O 成員” 記作：f(n)∈ O(g(n)) 但通常寫作：f(n)=O(g(n

53、))。（以上內(nèi)容參見《Intruduction to Algorithm》Chapter 3， Ω、Θ 相同）,60/90,[定理 大O比率定理] 對(duì)于函數(shù)f (n)和g (n)，若 存在，則 f (n)=O (g (n) )，當(dāng)且僅當(dāng)存在確定的常數(shù)c，有 ≤c。例：因?yàn)?，所以5n+2 = O(n) 因?yàn)?

54、 ，所以7n2+5n+2 = O(n2),61/90,定義1.2（下界函數(shù)） 如果存在兩個(gè)正常數(shù)c和n0，對(duì)于所有的n≥n0，有|f(n)| ≥ c|g(n)|，則記作f(n) = Ω(g(n))。含義：如果算法用n值不變的同一類數(shù)據(jù)在某臺(tái)機(jī)器上運(yùn)行，所用的時(shí)間總不小于|g(n)|的一個(gè)常數(shù)倍。函數(shù)f 至少是函數(shù)g 的c 倍，除非n <n0 。即是說(shuō)，當(dāng)n 充分大時(shí)，g 是f 的一個(gè)下界函數(shù)（在相差一個(gè)非零常數(shù)倍的

55、情況下）。,62/90,f(n)=2n+3=Ω(n)對(duì)所有n，2n+3≥2n, 可選c=2,n0=0。對(duì)于n≥n0,f(n)=2n+3≥2n，所以，f(n)=Ω(n).f(n)=10n2+4n+2=Ω(n2)對(duì)所有n，10n2+4n+2≥10n2，可選c=10,n0=0。對(duì)于n≥n0,f(n)=10n2+4n+2≥10n2，所以，f(n)=Ω(n2).,63/90,注：1. 通常情況下，下界函數(shù)也取單項(xiàng)的形式。2. 總是

56、試圖求出數(shù)量級(jí)最大的g(n)作為f(n)的下界函數(shù)，g(n)應(yīng)該盡量接近函數(shù)f(n)。其它具有和大O類似的性質(zhì)。,64/90,定義1.3（“平均情況”） 如果存在正常數(shù)c1，c2和n0，對(duì)于所有的n≥n0，有 c1|g(n)| ≤|f(n)| ≤ c2|g(n)|， 則記作含義：算法在最好和最壞情況下的計(jì)算時(shí)間就一個(gè)常數(shù)因子范圍內(nèi)而言是相同的?？煽醋鳎?既有 f(n) = Ω(g(n))，又有f(n) = Ο(g

57、(n))函數(shù)f 介于函數(shù)g 的c1和c2倍之間，即當(dāng)n充分大時(shí)， g 既是f 的下界，又是f 的上界。,65/90,例： 以二次函數(shù)為例，比如1/2n2-3n，要證明它是屬于Θ(n2)這個(gè)集合的，我們必須確定c1、c2和n0，這些常數(shù)不隨n改變，并且當(dāng)n≥n0以后，c1n2≤1/2n2-3n≤c2n2總是成立的。為此我們從不等式的每一邊都除以n2，得到c1≤1/2-3/n≤c2。見下圖：,66/90,這樣就很容易看出來(lái)，無(wú)論n取多少，

58、該函數(shù)一定小于1/2，因此c2=1/2，當(dāng)n=6時(shí)函數(shù)值為0，n>6時(shí)該函數(shù)都大于0，可以取n0=7，c1=1/14，這樣當(dāng)n≥n0時(shí)都有1/2-3/n≥c1。通過(guò)這個(gè)證明過(guò)程可以得出結(jié)論，當(dāng)n足夠大時(shí)任何an2+bn+c都夾在c1n2和c2n2之間，相對(duì)于n2項(xiàng)來(lái)說(shuō)bn+c的影響可以忽略，a可以通過(guò)選取合適的c1、c2來(lái)補(bǔ)償。,c1≤1/2-3/n≤c2,67/90,2）關(guān)于算法復(fù)雜度的討論,(1) 數(shù)量級(jí)的大小對(duì)算法的有效性有

59、決定性的影響。 以上界函數(shù)O(g(n))為例， 例：假設(shè)解決同一個(gè)問(wèn)題的兩個(gè)算法，它們都有n個(gè)輸入, 計(jì)算時(shí)間的數(shù)量級(jí)分別是n2和nlogn。則， n=1024：分別需要1048576和10240次運(yùn)算。 n=2048：分別需要4194304和22528次運(yùn)算。 可以看到：★ 同等規(guī)模n=1024下，計(jì)算量有近百倍的差距；★ 而在規(guī)模加倍后，一個(gè)Ο(n2)的算法計(jì)算時(shí)間增長(zhǎng)4

60、倍，而一個(gè)Ο(nlogn)算法則只增長(zhǎng)一倍多一點(diǎn)。,68/90,（2）算法時(shí)間復(fù)雜度的分類,根據(jù)上界函數(shù)的特性，可以將算法分為：多項(xiàng)式時(shí)間算法和指數(shù)時(shí)間算法。多項(xiàng)式時(shí)間算法：可用多項(xiàng)式函數(shù)對(duì)計(jì)算時(shí)間限界的 算法。常見的多項(xiàng)式限界函數(shù)有： Ο(1) < Ο(logn) < Ο(n) < Ο(nlogn) < Ο

61、(n2) < Ο(n3)指數(shù)時(shí)間算法：計(jì)算時(shí)間用指數(shù)函數(shù)限界的算法。常見的 指數(shù)時(shí)間限界函數(shù)： Ο(2n) < Ο(n！) < Ο(nn),復(fù)雜性越來(lái)越高,復(fù)雜性越來(lái)越高,如果f(n)=O(nk), 則稱f(n)是多項(xiàng)式界限的。,69/90,當(dāng)n取值較大時(shí)，指數(shù)時(shí)間算法和多項(xiàng)式時(shí)間算法在計(jì)算時(shí)間上非常懸殊。 計(jì)算時(shí)間的典型函數(shù)曲線,

62、70/90,計(jì)算時(shí)間函數(shù)值比較,表1.1 典型函數(shù)的值,,71/90,對(duì)算法復(fù)雜性的一般認(rèn)識(shí),當(dāng)數(shù)據(jù)集的規(guī)模很大時(shí)，要在現(xiàn)有的計(jì)算機(jī)系統(tǒng)上運(yùn)行具有比Ο(nlogn)復(fù)雜度還高的算法是比較困難的。指數(shù)時(shí)間算法只有在n取值非常小時(shí)才實(shí)用。要想在順序處理機(jī)上擴(kuò)大所處理問(wèn)題的規(guī)模，有效的途徑是降低算法的計(jì)算復(fù)雜度，而不是（僅僅依靠）提高計(jì)算機(jī)的速度。,72/90,（3）多項(xiàng)式定理,定理1 若A(n) = amnm+…+a1n+a0是一個(gè)m

63、次多項(xiàng)式，則有 A(n) = Ο(nm)即：變量n的固定階數(shù)為m的任一多項(xiàng)式，與此多項(xiàng)式的最高階nm同階。證明：取n0=1,當(dāng)n≥n0時(shí)，有 |A(n)|≤|am|nm+…+|a1|n+|a0| ＝(|am|+|am-1|/n+…+|a0|/nm) nm ≤(|am|+|am-1|+…+|a0|) nm

64、 令c= |am|+|am-1|+…+|a0|，即有|A(n)|≤ cnm 。證畢。應(yīng)用：如果一個(gè)算法的復(fù)雜性函數(shù)是多項(xiàng)式形式，則其階函數(shù)就可取該多項(xiàng)式的最高項(xiàng)。,73/90,3） 限界函數(shù)的性質(zhì),傳遞性：若 且 ，則（ 同）自反性：對(duì)稱性：若 ，則 。轉(zhuǎn)置對(duì)稱性：

65、 當(dāng)且僅當(dāng) (又稱為反對(duì)稱性、互對(duì)稱性),74/90,定理：設(shè)d(n)、e(n)、f(n)和g(n)是將非負(fù)整數(shù)映射到非負(fù)實(shí)數(shù)的函數(shù)，則(1)如果d(n)是O(f(n))，那么對(duì)于任何常數(shù)a>0,ad(n)是O(f(n))；常數(shù)不影響數(shù)量級(jí)(2)如果d(n)是O(f(n))， e(n)是O(g(n))，那么d(n)+e(n)是 O(f(n)+g(n))；加法原理(3)如果d(n)是O

66、(f(n))， e(n)是O(g(n))，那么d(n)e(n)是O(f(n)g(n)) 乘法原理(4)對(duì)于任意固定的x>0和a>1，nx是O(an)；(5)對(duì)于任意固定的x>0，lognx是O(logn)；這里x是常數(shù)(6)對(duì)于任意固定的常數(shù)x>0和y>0，logxn是O(ny)；,75/90,例：2n3+4n2logn=O(n3)證明：logn=O(n) 規(guī)則6 4n2lo

67、gn=O(4n3) 規(guī)則3 2n3+4n2logn=O(2n3+4n3) 規(guī)則2 2n3+4n3=O(n3) 規(guī)則1、多項(xiàng)式定理 2n3+4n2logn=O(n3),76/90,4）o,ω記號(hào),定義1.4 o記號(hào)形式1：對(duì)任意正常數(shù)c，存在常數(shù)n0＞0，使對(duì)所有的n≥n0，有|f(n)| ≤ c|g(n)|，則記作：f(n) = o(g(n))。形式2：若

68、 則記f(n) = o(g(n))。例：2n = o(n2)，但2n2≠ o(n2),77/90,O和o的區(qū)別,O：o：在o表示中，當(dāng)n趨于無(wú)窮時(shí)，f(n)相對(duì)于g(n)來(lái)說(shuō)已經(jīng)不重要了。,78/90,定義1.5 ω記號(hào)形式1：對(duì)任意正常數(shù)c，存在常數(shù)n0＞0，使對(duì)所有的n≥n0，有c|g(n)|≤|f(n)| ，則記作： f(n) = ω(g(n))。形式2：若