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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

23、 for i←2 to n do //從第二個元素開始循環(huán) item←A(i); //將A[i]放到臨時變量item中 j←i-1 //從后往前查找當前元素的插入位置 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,基于上述算法，思考：這個算法描述正確嗎？能行、確定、輸入、輸出、有窮？ 正確性證明運算得快嗎？ 時間復(fù)雜度分析使用了多少內(nèi)存？ 空間復(fù)雜度分析進一步我們需要回答：它能夠應(yīng)用到那些領(lǐng)域？

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

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

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

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

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

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

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

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

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

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

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

37、頻率計數(shù)：算法中語句或運算的執(zhí)行次數(shù)，從算法的控制流程得來。 順序結(jié)構(gòu)中的運算/語句：執(zhí)行次數(shù)計為1 嵌套結(jié)構(gòu)中的運算/語句：執(zhí)行次數(shù)等于循環(huán)執(zhí)行的次數(shù) ★ 控制流程分析的關(guān)鍵：確定算法中使用的嵌套結(jié)構(gòu)，包括循環(huán)語句、嵌套調(diào)用等。,47/90,例：執(zhí)行次數(shù)的統(tǒng)計 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,★ 頻率計數(shù)通常是問題規(guī)模n的函數(shù)：n0,n,n2,… ★ 算法的執(zhí)行時間是算法中各類運算執(zhí)行

40、時間之和，正比于各類運算的頻率計數(shù)之和。,49/90,例：插入排序 procedure INSERTIONSORT(A,n) //將A(1：n)中的元素按非降次序分類，n≥1// 執(zhí)行次數(shù) 單位執(zhí)行時間 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 最壞情況時間：,50/90

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

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

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

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

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

49、，除非n<n0。即是說，當n 充分大時，g 是f 的一個上界函數(shù)（在相差一個非零常數(shù)倍的情況下）。f(n)的數(shù)量級就是g(n)。,57/90,g(n)是通過對算法中運算使用情況的分析，得出的函數(shù)表達式，通常情況下，取函數(shù)式里的最高次項，舍掉低階項和常數(shù)（因為低階項和常數(shù)最終被湮滅在高次項里），且忽略系數(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ù)量級最小的g(n)作為f(n)的上界函數(shù)，即， g(n)應(yīng)該盡量接近函數(shù)f(n)。如若：3n+2=O(n2) 則是松散的界限；而：3n+2=O(n) 就是較好的界限。數(shù)量級越小，

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

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

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

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

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

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

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

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

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

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

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

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

63、次多項式，則有 A(n) = Ο(nm)即：變量n的固定階數(shù)為m的任一多項式，與此多項式的最高階nm同階。證明：取n0=1,當n≥n0時，有 |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)用：如果一個算法的復(fù)雜性函數(shù)是多項式形式，則其階函數(shù)就可取該多項式的最高項。,73/90,3） 限界函數(shù)的性質(zhì),傳遞性：若 且 ，則（ 同）自反性：對稱性：若 ，則 。轉(zhuǎn)置對稱性：

65、 當且僅當 (又稱為反對稱性、互對稱性),74/90,定理：設(shè)d(n)、e(n)、f(n)和g(n)是將非負整數(shù)映射到非負實數(shù)的函數(shù)，則(1)如果d(n)是O(f(n))，那么對于任何常數(shù)a>0,ad(n)是O(f(n))；常數(shù)不影響數(shù)量級(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)對于任意固定的x>0和a>1，nx是O(an)；(5)對于任意固定的x>0，lognx是O(logn)；這里x是常數(shù)(6)對于任意固定的常數(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、多項式定理 2n3+4n2logn=O(n3),76/90,4）o,ω記號,定義1.4 o記號形式1：對任意正常數(shù)c，存在常數(shù)n0＞0，使對所有的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表示中，當n趨于無窮時，f(n)相對于g(n)來說已經(jīng)不重要了。,78/90,定義1.5 ω記號形式1：對任意正常數(shù)c，存在常數(shù)n0＞0，使對所有的n≥n0，有c|g(n)|≤|f(n)| ，則記作： f(n) = ω(g(n))。形式2：若