算法設(shè)計(jì)與分析王佳01概述

1、主講教師 james. 信息學(xué)院,算法設(shè)計(jì)與分析,2,課程前言,一、什么是算法,事情太多了，怎么才能讓計(jì)算機(jī)幫我做呢,實(shí)際問題,程序,數(shù)學(xué)模型,算法,算法是指解題方案準(zhǔn)確而完整的描述,3,實(shí)際問題：超級(jí)女聲收入到底有多少,程序: Main() .,數(shù)學(xué)模型：總收入=短信收入+廣告收入,算法： 收入( 今天 ) if (比賽日程沒結(jié)束) 短信收入 = 今天短信數(shù) * 短信單價(jià); if (今天有比賽) 廣告收入 = 廣告單價(jià) * 廣告時(shí)長(zhǎng); else return 收入 = 短信收入 + 廣告收入; 總收入( ) for( i = 開始日期; i = 最后一天; i+ ) 總收入 += 收入( i

2、 ); return 總收入；,4,舉個(gè)例子：排序 問題描述：將一組數(shù)按從小到大的順序整理有序 基本思想：小的數(shù)往前排，大的數(shù)往后排 怎么排？算法 冒泡排序 選擇排序 歸并排序 快速排序 堆排序 Shell排序,每種算法都是一組特定的規(guī)則，規(guī)定了一種處理數(shù)據(jù)的運(yùn)算方法,課程前言,5,問題：既然每種方法都可以實(shí)現(xiàn)排序之目的，何必費(fèi)心研究這么多排序算法？ 其一：“瞎想”，就像玩智力游戲，人們樂衷于尋找不同的方法解決各種各樣的問題。 其二：研究的需要，算法和算法間是有區(qū)別的，我們有必要去研究，去分析。 性質(zhì)不同：穩(wěn)定、不穩(wěn)定 性能不同：速度、空間 適用場(chǎng)合不同 其三，應(yīng)用的需求，問題有千百萬種，沒有

3、萬能的算法適合所有的應(yīng)用。需要我們找出算法的設(shè)計(jì)規(guī)律，并設(shè)計(jì)出解決問題的新算法 怎么選擇：根據(jù)性能、結(jié)合需求、綜合選擇 如何了解每種算法的性能？算法的分析,6,二、算法分析 了解算法的性能： 算法速度：快還是慢？如何衡量？怎么比較？ 空間使用：大還是小？如何衡量？怎么比較？ 其它方面的性質(zhì)等,課程前言,7,三、為什么要學(xué)習(xí)算法 1. 編程需要 任何程序都需要算法(the core of computer science) 憑借一句話獲得圖靈獎(jiǎng)的Pascal之父瑞士計(jì)算機(jī)科學(xué)家尼古拉斯沃斯Nicklaus Wirth 程序=數(shù)據(jù)結(jié)構(gòu)+算法 (Algorithm+Data Structures=P

4、rograms) 算法是計(jì)算機(jī)科學(xué)的基礎(chǔ)，更是程序的基石，只有具有良好的算法基礎(chǔ)才能成為訓(xùn)練有素的軟件人才,課程前言,8,2. 改造世界的需要 世界上還有很多很多的問題等待你解決，有無數(shù)的程序等待你去編。 3. 國(guó)家綜合實(shí)力的體現(xiàn)（大） 從軟實(shí)力的角度，算法是國(guó)家科技生產(chǎn)力的核心。是國(guó)家綜合實(shí)力的體現(xiàn),9,四、頭疼 問題太多，算法太多了，學(xué)不過來 是的，都學(xué)過來是不可能的。甚至專一門已經(jīng)很了不起。 學(xué)習(xí)算法設(shè)計(jì)與分析的策略、技術(shù)和方法，把握解決問題的規(guī)律，為設(shè)計(jì)更復(fù)雜、更有效的算法奠定基礎(chǔ)。 需要同學(xué)們不斷學(xué)習(xí)，深入思考，創(chuàng)新設(shè)計(jì),課程前言,10,五、學(xué)習(xí)過程：痛苦并快樂著 1.枯燥的過程 繁

5、vs煩：學(xué)習(xí)一個(gè)算法如同做一道數(shù)學(xué)題，熟能生巧 2.智慧的積累 方法的掌握、技術(shù)的升華 3.理論的貢獻(xiàn) 算法成就或在于理論的貢獻(xiàn)，而不僅僅是技術(shù)的提高。 如何成就好算法：好思想+好技術(shù),課程前言,11,六、好算法 從理論的角度說，好算法應(yīng)該有較低的時(shí)間復(fù)雜度（高速）和空間復(fù)雜度（低耗），但好的算法還要依靠好的算法實(shí)現(xiàn)，需要理論與技術(shù)、技巧的結(jié)合才能最終實(shí)現(xiàn)好的算法。 從應(yīng)用的角度說，能有效地解決問題的算法都是好算法不管黑貓白貓，抓住老鼠就是好貓；不管A算法、B算法，能解決問題就是好算法,課程前言,12,概述,課程名稱：算法設(shè)計(jì)與分析 Design and Analysis of Algorit

6、hms 先修課程 C/C+語言程序設(shè)計(jì)，數(shù)據(jù)結(jié)構(gòu) 課程核心 介紹算法設(shè)計(jì)與分析的基本理論、方法和技術(shù)， 奠定算法設(shè)計(jì)的基礎(chǔ) 教材 十一五國(guó)家級(jí)規(guī)劃教材，算法設(shè)計(jì)與分析陳慧南編著，電子工業(yè)出版社,13,主要參考書 計(jì)算機(jī)算法基礎(chǔ)， 余祥宣等編著， 華中科技大學(xué)出版社 Introduction to algorithms, Thomas H. Cormen,etc., second edition, The MIT Press. Algorithm Design，Michael T. Goodrich 算法設(shè)計(jì)與分析，王曉東，清華大學(xué)出版社,14,其它參考書 The Art of Computer

7、 Programming, Donald E.Knuth. Volume 1-3, Second Edition. Data Structures, Algorithms, and Applications in C+(Part 3) Sartaj Sahni, China Machine Press etc,15,1.1 算法的定義及特性,1. 什么是算法？ 算法如數(shù)字、計(jì)算一樣，是一個(gè)基本概念。 算法是解一確定類問題的任意一種特殊的方法。 在計(jì)算機(jī)科學(xué)中，算法是使用計(jì)算機(jī)解一類問題的精確、有效方法的代名詞； 算法是一組有窮的規(guī)則，它規(guī)定了解決某一特定類型問題的一系列運(yùn)算,16,對(duì)算法概念的

8、理解 算法由運(yùn)算組成 算術(shù)運(yùn)算、邏輯運(yùn)算、賦值運(yùn)算、過程調(diào)用 算法有其特殊性 解決不同問題的算法是不相同的，有沒有一個(gè)萬能的算法？ 算法是有窮的計(jì)算過程 靜態(tài)上：規(guī)則/運(yùn)算/語句的數(shù)量有窮 動(dòng)態(tài)上：計(jì)算過程/計(jì)算時(shí)間有限,17,我們已經(jīng)接觸過的算法： 排序算法：將已知的n個(gè)元素按照關(guān)鍵值大小的非增/非降順序重新排列。 如：冒泡排序、插入排序、歸并排序 查找算法：從已知的元素集合中找出滿足要求的一個(gè)或一組元素。 如：順序查找、二分查找 圖算法：在已知的圖中找出滿足某些性質(zhì)的結(jié)點(diǎn)或邊。 如：最短路徑算法、最小成本生成樹,18,思考,我們學(xué)會(huì)了解決一個(gè)個(gè)具體問題的算法，那么在這些算法的設(shè)計(jì)中有沒有一

9、些共性的東西？有沒有可以總結(jié)出來的規(guī)律、規(guī)則和方法？這些規(guī)律、規(guī)則和方法對(duì)于其它算法的設(shè)計(jì)有沒有指導(dǎo)意義？ 能不能找到一些算法設(shè)計(jì)的一般策略、技術(shù)和方法,19,2. 算法的五個(gè)重要特性,輸入、輸出、確定性、能行性、有窮性,1）輸入 每個(gè)算法都有0個(gè)或多個(gè)輸入。這些輸入是在算法開始之前給出的量，取自于特定的對(duì)象集合定義域 2）輸出 一個(gè)算法產(chǎn)生一個(gè)或多個(gè)輸出，這些輸出是同輸入有某種特定關(guān)系的量,20,3）確定性：算法使用的每種運(yùn)算必須要有確切的定義，不能有二義性。 例：不符合確定性的運(yùn)算 23/0 計(jì)算5+3或計(jì)算7-3 未賦值變量參與運(yùn)算,如果a = 6 那么x該取什么值呢,再如： if (a

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

11、行了有窮步的運(yùn)算之后終止,計(jì)算過程：滿足確定性、能行性、輸入、輸出， 但不一定滿足有窮性的一組規(guī)則。 算法和計(jì)算過程的關(guān)系： 計(jì)算過程：操作系統(tǒng)(不終止的運(yùn)行過程) 算法是“可以終止的計(jì)算過程,24,時(shí)效性：實(shí)際問題往往都有時(shí)間要求。 例：國(guó)際象棋（啟發(fā)） 數(shù)值天氣預(yù)報(bào) 只有在要求的時(shí)間內(nèi)解決問題才是有意義的,25,1.2 問題和問題求解,問題求解（problem solving）是尋找一種方法來實(shí)現(xiàn)目標(biāo)。 問題求解過程（problem solving process）是人們通過使用問題領(lǐng)域知識(shí)來理解和定義問題，并憑借自身的經(jīng)驗(yàn)和知識(shí)去選擇和使用適當(dāng)?shù)膯栴}求解策略、技術(shù)和工具，將一個(gè)問題描述轉(zhuǎn)

12、換成問題解的過程。 計(jì)算機(jī)求解問題的關(guān)鍵之一是尋找一種問題求解策略（problem solving strategy），得到求解問題的算法，從而得到問題的解,26,問題求解過程,理解問題（understand the problem） 設(shè)計(jì)方案（devise a plan） 實(shí)現(xiàn)方案（carry out the plan） 回顧復(fù)查（look back,27,算法問題求解過程,算法分類 一個(gè)精確算法（exact algorithm）總能保證求得問題的解。 一個(gè)啟發(fā)式算法（heuristic algorithm）通過使用某種規(guī)則、簡(jiǎn)化或智能猜測(cè)來減少問題求解時(shí)間,28,對(duì)于最優(yōu)化問題，一個(gè)算法如

13、果致力于尋找近似解而不是最優(yōu)解，被稱為近似算法（approximation algorithm）。 如果在算法中需做出某些隨機(jī)選擇，隨機(jī)算法（randomized algorithm,29,與算法學(xué)習(xí)相關(guān)的內(nèi)容,五個(gè)方面：設(shè)計(jì)、表示、證明、分析、測(cè)試,1）設(shè)計(jì)：構(gòu)思算法的處理規(guī)則，創(chuàng)造性的活動(dòng)。 2）表示：用語言把算法描述出來。 自然語言 流程圖 偽代碼 程序設(shè)計(jì)語言,30,與算法學(xué)習(xí)相關(guān)的內(nèi)容,3）證明：證明算法的正確性。 證明算法對(duì)所有輸入都停止 證明對(duì)每個(gè)輸入都產(chǎn)生正確結(jié)果 調(diào)試程序程序正確性證明 程序調(diào)試只能證明程序有錯(cuò)，不能證明程序無錯(cuò)誤,31,4）分析：對(duì)算法的時(shí)、空特性做定性、定

14、量分析，以了解算法的性質(zhì)。 5）測(cè)試：將算法變成程序，放到計(jì)算機(jī)上運(yùn)行，觀察運(yùn)行情況,編程中的調(diào)試：排錯(cuò)過程?！罢{(diào)試只能指出有錯(cuò)誤，而不能指出它們不存在錯(cuò)誤” 運(yùn)行中的測(cè)試：分析過程。驗(yàn)證分析結(jié)論，進(jìn)一步優(yōu)化算法設(shè)計(jì)。 本課程集中于學(xué)習(xí)算法的設(shè)計(jì)與分析。通過學(xué)習(xí)，掌握計(jì)算機(jī)算法設(shè)計(jì)和分析基本策略與方法，為設(shè)計(jì)更復(fù)雜、更有效的算法奠定基礎(chǔ),32,1.3 分析算法基礎(chǔ),從一個(gè)例子開始講起：插入算法 插入分類算法描述： 輸入：n個(gè)元素存放在數(shù)組A中：A0An-1，無序 輸出：按照從小到大的順序重新整理有序的數(shù)組A1An 設(shè)計(jì)思路： 1. 將第一個(gè)元素（A0）看作只有一個(gè)元素的有序子序列； 2. 置循

15、環(huán) i=1 to n-1，將Ai插入到由A0Ai-1元素組成的有序子序列。 思考問題： 上述設(shè)計(jì)思路對(duì)嗎？ 如何實(shí)現(xiàn),33,算法描述： procedure INSERTIONSORT(A,n) A(0)- /A0做監(jiān)視哨 for i2 to n do /從第二個(gè)元素開始循環(huán) itemA(i); /將Ai放到臨時(shí)變量item中 ji-1 /從后往前查找當(dāng)前元素的插入位置 while itemA(j) do A(j+1)A(j); /比item大的元素往后移一位 jj-1; /繼續(xù)往前查找 repeat A(j+1) item; /將item插入到正確的位置上 repeat end INSERTI

16、ONSORT,34,基于上述算法，思考： 這個(gè)算法描述正確嗎？ 能行、確定、輸入、輸出、有窮？ 正確性證明 運(yùn)算得快嗎？ 時(shí)間復(fù)雜度分析 使用了多少內(nèi)存？ 空間復(fù)雜度分析 進(jìn)一步我們需要回答： 它能夠應(yīng)用到那些領(lǐng)域？ 要做深入進(jìn)一步分析 利用不同語言實(shí)現(xiàn)需要那些技巧? 實(shí)現(xiàn),35,1. 分析算法的目的,算法選擇的需要：對(duì)同一個(gè)問題可以設(shè)計(jì)不同的算法，不同的算法對(duì)時(shí)間和空間需求是不同的 算法優(yōu)化的需要：有沒有可以改進(jìn)的地方，以使算法工作的更好？ 分析算法的目的在于： 通過對(duì)算法的分析了解算法的性能 1）可以在解決同一問題的不同算法之間比較性能的好壞，從而運(yùn)行好的算法，改進(jìn)差的算法，避免無益的人力

17、和物力浪費(fèi)。 2）可以對(duì)算法的性質(zhì)作深入了解，從而可以進(jìn)一步優(yōu)化算法，讓其更好地工作,36,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ī)硬件和編制程序的語言無關(guān)。 ti ：是運(yùn)算i在實(shí)際的計(jì)算機(jī)上每執(zhí)行一次所用的時(shí)間 與程序設(shè)計(jì)語言和計(jì)算機(jī)硬件有關(guān)。 如何確定算法使用了哪些運(yùn)算,每種運(yùn)算的fi和ti又是多少,37,運(yùn)算的分類,依照運(yùn)算的時(shí)間特性，將運(yùn)算分為時(shí)間囿界于常數(shù)的運(yùn)算和時(shí)間非囿界于常數(shù)的運(yùn)算。 囿界：限于. 時(shí)間囿界于常數(shù)的運(yùn)算： 基本

18、算術(shù)運(yùn)算，如整數(shù)、浮點(diǎn)數(shù)的加、減、乘、除 字符運(yùn)算、賦值運(yùn)算、過程調(diào)用等 特點(diǎn)：盡管每種運(yùn)算執(zhí)行時(shí)間不同，但一般只花一個(gè)固定量的時(shí)間（單位時(shí)間）就可完成。 例： 1+1 = 2 vs 10000+10000 = 20000 100*100 = 10000 vs 10000*10000 = 100000000 CALL INSERTIONSORT,38,更一般的情況,設(shè)有n種運(yùn)算c1，c2，cn，它們的執(zhí)行時(shí)間分別是t1，t2，tn。 令t0=max(t1，t2，tn)，則每種運(yùn)算執(zhí)行一次的時(shí)間都可以用t0進(jìn)行限界(上界)。 視t0為一個(gè)單位時(shí)間，則這些運(yùn)算“理論”上都可視為僅花一個(gè)固定的單位時(shí)

19、間t0即可完成的運(yùn)算 稱具有這種性質(zhì)的運(yùn)算為時(shí)間囿界于常數(shù)的運(yùn)算,39,運(yùn)算的分類,時(shí)間非囿界于常數(shù)的運(yùn)算： 字符串操作：與字符串中字符的數(shù)量成正比 例：字符串的比較運(yùn)算（strcmp） 記錄操作：與記錄的屬性數(shù)、屬性類型等有關(guān) 特點(diǎn)：運(yùn)算時(shí)間與操作數(shù)相關(guān)，每次執(zhí)行的時(shí)間是一個(gè)不定的量,40,怎么分析時(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（Str

20、ing）* tchar 故：分析時(shí)間非囿界于常數(shù)的運(yùn)算時(shí)，將其分解成若干時(shí)間囿界于常數(shù)的運(yùn)算即可,41,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)工作情況,42,注：編制測(cè)試數(shù)據(jù)對(duì)算法分析與程序調(diào)試都是關(guān)鍵的，但目的不同。 算法分析數(shù)據(jù)集：反映算法的典型執(zhí)行情況（最好、最壞、平均） 調(diào)試程序數(shù)據(jù)

21、集：排錯(cuò)。力求走到程序的每個(gè)分支，驗(yàn)證各種情況下程序執(zhí)行的正確性,43,4. 如何進(jìn)行算法分析,對(duì)算法的全面分析將分兩個(gè)階段進(jìn)行：事前分析和事后測(cè)試（理論分析和程序測(cè)試）。 事前分析：求算法時(shí)間/空間復(fù)雜度的限界函數(shù)。 限界函數(shù)通常是關(guān)于問題規(guī)模n的特征函數(shù)，被表示成、或的形式。 如歸并排序的O(nlogn)。 特征函數(shù)是通過分析算法的控制邏輯得來的，是對(duì)算法所用運(yùn)算執(zhí)行次數(shù)的統(tǒng)計(jì)結(jié)果。與使用的程序設(shè)計(jì)語言和計(jì)算機(jī)硬件無關(guān),44,事后測(cè)試：將算法編制成程序，放到實(shí)際的計(jì)算機(jī)上運(yùn)行，收集程序的執(zhí)行時(shí)間和空間占用等統(tǒng)計(jì)資料，然后進(jìn)行分析判斷。 事后測(cè)試與物理實(shí)現(xiàn)直接有關(guān)。 算法分析主要集中于與物理

22、實(shí)現(xiàn)無關(guān)的事前分析階段獲取算法的理論時(shí)間/空間復(fù)雜度,45,1）事前分析,目標(biāo)：獲取算法的時(shí)間（空間）復(fù)雜度函數(shù)，從理論上分析算法性能的好壞。 可以分為時(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)于問題規(guī)模n的特征函數(shù)。 算法性能有最好、平均、最壞等情況，與數(shù)據(jù)配置有關(guān)。分析典型的數(shù)據(jù)配置，了解算法在各種情況下的執(zhí)行情況,46,空間分析： 分析算法中各類變量的定義情況 分析算法的嵌套結(jié)構(gòu)中變量的使用情況 將空間占用量表示成為問題

23、規(guī)模n的特征函數(shù)。 空間占用有最大、平均、最少等情況，與數(shù)據(jù)配置有關(guān)。分析典型的數(shù)據(jù)配置，了解算法在各種情況下的空間占用情況,47,如何進(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í)間的程序塊，如一條語句、一個(gè)過程或函數(shù)等 頻率計(jì)數(shù)：算法中語句或運(yùn)算的執(zhí)行次數(shù)，從算法的控制流程得來。 順序結(jié)構(gòu)中的運(yùn)算/語句：執(zhí)行次數(shù)計(jì)為1 嵌套結(jié)構(gòu)中的運(yùn)算/語句：執(zhí)行次數(shù)等于循環(huán)執(zhí)行的次數(shù) 控制流程分析的關(guān)鍵：確定算法中使用的嵌套結(jié)構(gòu)，包括循環(huán)語句、嵌套調(diào)用等,48,例：執(zhí)行次數(shù)的統(tǒng)計(jì) xx+y for i 1 to n d

24、o for i 1 to n do x x + y for j 1 to n do repeat x x +y repeat repeat (a) (b) (c) 分析： (a)： xx+y執(zhí)行了1次 (b)： xx+y執(zhí)行了n次 (c)： xx+y執(zhí)行了n2次,49,頻率計(jì)數(shù)通常是問題規(guī)模n的函數(shù)：n0,n,n2, 算法的執(zhí)行時(shí)間是算法中各類運(yùn)算執(zhí)行時(shí)間之和，正比于各類運(yùn)算的頻率計(jì)數(shù)之和,50,例：插入排序 procedure INSERTIONSORT(A,n) /將A(1：n)中的元素按非降次序分類，n1/ 執(zhí)行次數(shù) 單位執(zhí)行時(shí)間 A(0)-/設(shè)置初始邊界值 1 t1 for j2 to

25、 n do /A(1:j-1)已分類/ n-1 t2 itemA(j); n-1 t3 ij-1 n-1 t4 while itemA(i) do /0ij/ 最多i次,最少1次 t5 A(i+1)A(i); 最多i-1次,最少0次 t6 ii-1; 最多i-1次,最少0次 t4 repeat A(i+1) item; n-1次 t7 repeat end INSERTIONSORT 最壞情況時(shí)間,51,令 t0=max(t1,t2,t3,t4,t5,t6,t7)，則,最壞情況,最好情況,52,事前分析的結(jié)果與所使用的機(jī)器及其他環(huán)境因素?zé)o關(guān) （如程序設(shè)計(jì)語言、編譯器），只與算法本身的控制流程有

26、關(guān)。 對(duì)算法最主要的部分進(jìn)行分析,抓住主要矛盾，如插入排序中,可以僅集中于對(duì)for/while雙重嵌套循環(huán)的分析，而忽略順序或執(zhí)行次數(shù)低的部分,53,函數(shù)表達(dá)式的數(shù)量級(jí)（階） 函數(shù)表達(dá)式中的最高次項(xiàng)的次數(shù)，是衡量頻率計(jì)數(shù)的“大小”的一種測(cè)度。 數(shù)量級(jí)從本質(zhì)上反映了算法復(fù)雜度的高低 數(shù)量級(jí)越小，算法的復(fù)雜度越低，同等規(guī)模下算法執(zhí)行時(shí)間越短。反之，數(shù)量級(jí)越大，算法的復(fù)雜度越高，同等規(guī)模下算法執(zhí)行時(shí)間越長(zhǎng)。 例：假如求解同一個(gè)問題的三個(gè)算法分別具有n， n2 ， n3數(shù)量級(jí)。 若n=10，則可能的執(zhí)行時(shí)間將分別是10，100，1000個(gè)單位時(shí)間,54,限界函數(shù)：用頻率計(jì)數(shù)函數(shù)表達(dá)式中的最高次項(xiàng)表示限

27、界函數(shù)記為： g(n)。 g(n)通常是關(guān)于n的形式簡(jiǎn)單的函數(shù)式，如：logn，nlogn，n2等 不同算法的g(n)有不同的具體形式。 g(n)通常是對(duì)算法中最復(fù)雜的計(jì)算部分分析而來的。 g(n)忽略了函數(shù)表達(dá)式中次數(shù)較低的“次要”項(xiàng)，體現(xiàn)了算法復(fù)雜性的最本質(zhì)特征。 g(n)通常取單項(xiàng)的形式。 空間特性分析（與時(shí)間特性的分析類似，略,55,2）事后測(cè)試,把算法編制成程序，在實(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ì)的算法,56,5. 計(jì)算時(shí)間的漸近表示,算法時(shí)間/空間復(fù)雜度的限界函

28、數(shù)常用的有三個(gè)：上界函數(shù)、下界函數(shù)、“均值”函數(shù)。定義如下： 記：算法的實(shí)際計(jì)算時(shí)間為f(n)，計(jì)算時(shí)間的限界函數(shù)為g(n)，其中， n是問題規(guī)模的某種測(cè)度。 f(n)是與機(jī)器及語言有關(guān)的量。 g(n)是事前分析的結(jié)果，一個(gè)形式簡(jiǎn)單的函數(shù)，與頻率計(jì)數(shù)有關(guān)、而與機(jī)器及語言無關(guān),57,1）O、記號(hào),定義1. 1（上界函數(shù)）如果存在兩個(gè)正常數(shù)c和n0，對(duì)于所有的nn0，有|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倍，除非nn0。即是

29、說，當(dāng)n 充分大時(shí)，g 是f 的一個(gè)上界函數(shù)（在相差一個(gè)非零常數(shù)倍的情況下）。 f(n)的數(shù)量級(jí)就是g(n,58,g(n)是通過對(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ù)，可看作n0 4n+3=O(n): 可取c5，n03 100n+6=O(n): 可取 c=101，n06 62n+n2=O(2n): 可取c =7，n0=4 10n2+4n+3=O(n2) 3log n + 2n + n2 =O(n2) nlog n +n2=O(n2,59,注：

30、 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í)越小，限界越精確。 2不要產(chǎn)生錯(cuò)誤界限。 如，n2+100n+6，當(dāng)nc-100 就有 n2+100n+6cn。 提示：注意大系數(shù)低次項(xiàng)的影響 同理，3n2+42n=O(n)也是錯(cuò)誤的,60,3 f(n)=O(g(n)不能寫成g(n)=O(f(n)。 f(n)與g(n)并不等價(jià)，這里的等號(hào)也并不是通常相等的含義。 O更精確的定義可以用集合表示： O(g(n)=f(n)|f(n)滿足：存在正的常數(shù)c 和

31、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)。 （以上內(nèi)容參見Intruduction to AlgorithmChapter 3， 、 相同,61,定理 大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)?，所以7n2+5n+2 = O(n2,62,定義1.2（下界函數(shù)） 如果存在兩個(gè)正常數(shù)c和n0，對(duì)于所

32、有的nn0，有|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 。即是說，當(dāng)n 充分大時(shí)，g 是f 的一個(gè)下界函數(shù)（在相差一個(gè)非零常數(shù)倍的情況下,63,f(n)=2n+3=(n) 對(duì)所有n，2n+32n, 可選c=2,n0=0。對(duì)于nn0,f(n)=2n+32n，所以，f(n)=(n). f(n)=10n2+4n+2=(n2) 對(duì)所有n，10n2+4n+210n2，可選c=10,n0=0。對(duì)于nn0,f(n)=10n2+4n+210n

33、2，所以，f(n)=(n2,64,注： 1. 通常情況下，下界函數(shù)也取單項(xiàng)的形式。 2. 總是試圖求出數(shù)量級(jí)最大的g(n)作為f(n)的下界函數(shù)，g(n)應(yīng)該盡量接近函數(shù)f(n)。 其它具有和大O類似的性質(zhì),65,定義1.3（“平均情況”） 如果存在正常數(shù)c1，c2和n0，對(duì)于所有的nn0，有 c1|g(n)| |f(n)| c2|g(n)|， 則記作 含義： 算法在最好和最壞情況下的計(jì)算時(shí)間就一個(gè)常數(shù)因子范圍內(nèi)而言是相同的?？煽醋鳎?既有 f(n) = (g(n)，又有f(n) = (g(n) 函數(shù)f 介于函數(shù)g 的c1和c2倍之間，即當(dāng)n充分大時(shí)， g 既是f 的下界，又是f 的上界,66

34、,例： 以二次函數(shù)為例，比如1/2n2-3n，要證明它是屬于(n2)這個(gè)集合的，我們必須確定c1、c2和n0，這些常數(shù)不隨n改變，并且當(dāng)nn0以后，c1n21/2n2-3nc2n2總是成立的。為此我們從不等式的每一邊都除以n2，得到c11/2-3/nc2。見下圖,67,這樣就很容易看出來，無論n取多少，該函數(shù)一定小于1/2，因此c2=1/2，當(dāng)n=6時(shí)函數(shù)值為0，n6時(shí)該函數(shù)都大于0，可以取n0=7，c1=1/14，這樣當(dāng)nn0時(shí)都有1/2-3/nc1。通過這個(gè)證明過程可以得出結(jié)論，當(dāng)n足夠大時(shí)任何an2+bn+c都夾在c1n2和c2n2之間，相對(duì)于n2項(xiàng)來說bn+c的影響可以忽略，a可以通過

35、選取合適的c1、c2來補(bǔ)償,c11/2-3/nc2,68,2）關(guān)于算法復(fù)雜度的討論,1) 數(shù)量級(jí)的大小對(duì)算法的有效性有決定性的影響。 以上界函數(shù)O(g(n)為例， 例：假設(shè)解決同一個(gè)問題的兩個(gè)算法，它們都有n個(gè)輸入, 計(jì)算時(shí)間的數(shù)量級(jí)分別是n2和nlogn。則， n=1024：分別需要和10240次運(yùn)算。 n=2048：分別需要和22528次運(yùn)算。 可以看到： 同等規(guī)模n=1024下，計(jì)算量有近百倍的差距； 而在規(guī)模加倍后，一個(gè)(n2)的算法計(jì)算時(shí)間增長(zhǎng)4倍，而一個(gè)(nlogn)算法則只增長(zhǎng)一倍多一點(diǎn),69,2）算法時(shí)間復(fù)雜度的分類,根據(jù)上界函數(shù)的特性，可以將算法分為：多項(xiàng)式時(shí)間算法和指數(shù)時(shí)間

36、算法。 多項(xiàng)式時(shí)間算法：可用多項(xiàng)式函數(shù)對(duì)計(jì)算時(shí)間限界的 算法。常見的多項(xiàng)式限界函數(shù)有： (1) (logn) (n) (nlogn) (n2) (n3) 指數(shù)時(shí)間算法：計(jì)算時(shí)間用指數(shù)函數(shù)限界的算法。常見的 指數(shù)時(shí)間限界函數(shù)： (2n) (n！) (nn,復(fù)雜性越來越高,復(fù)雜性越來越高,如果f(n)=O(nk), 則稱f(n)是多項(xiàng)式界限的,70,當(dāng)n取值較大時(shí)，指數(shù)時(shí)間算法和多項(xiàng)式時(shí)間算法在計(jì)算時(shí)間上非常懸殊。 計(jì)算時(shí)間的典型函數(shù)曲線,71,計(jì)算時(shí)間函數(shù)值比較,表1.1 典型函數(shù)的值,72,對(duì)算法復(fù)雜性的一般認(rèn)識(shí),當(dāng)數(shù)據(jù)集的規(guī)模很大時(shí)，要在現(xiàn)有的計(jì)算機(jī)系統(tǒng)上運(yùn)行具有比(nlogn)復(fù)雜度還高的

37、算法是比較困難的。 指數(shù)時(shí)間算法只有在n取值非常小時(shí)才實(shí)用。 要想在順序處理機(jī)上擴(kuò)大所處理問題的規(guī)模，有效的途徑是降低算法的計(jì)算復(fù)雜度，而不是（僅僅依靠）提高計(jì)算機(jī)的速度,73,3）多項(xiàng)式定理,定理1 若A(n) = amnm+a1n+a0是一個(gè)m次多項(xiàng)式，則有 A(n) = (nm) 即：變量n的固定階數(shù)為m的任一多項(xiàng)式，與此多項(xiàng)式的最高階nm同階。 證明：取n0=1,當(dāng)nn0時(shí)，有 |A(n)|am|nm+|a1|n+|a0| (|am|+|am-1|/n+|a0|/nm) nm (|am|+|am-1|+|a0|) nm 令c= |am|+|am-1|+|a0|，即有|A(n)| cnm

38、 。證畢。 應(yīng)用：如果一個(gè)算法的復(fù)雜性函數(shù)是多項(xiàng)式形式，則其階函數(shù)就可取該多項(xiàng)式的最高項(xiàng),74,3） 限界函數(shù)的性質(zhì),傳遞性：若 且 ，則（ 同） 自反性： 對(duì)稱性：若 ，則 。 轉(zhuǎn)置對(duì)稱性： 當(dāng)且僅當(dāng) (又稱為反對(duì)稱性、互對(duì)稱性,75,定理：設(shè)d(n)、e(n)、f(n)和g(n)是將非負(fù)整數(shù)映射到非負(fù)實(shí)數(shù)的函數(shù)，則 (1)如果d(n)是O(f(n)，那么對(duì)于任何常數(shù)a0,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(f(n)， e(n)是O(g(n)

39、，那么d(n)e(n)是O(f(n)g(n) 乘法原理 (4)對(duì)于任意固定的x0和a1，nx是O(an)； (5)對(duì)于任意固定的x0，lognx是O(logn)；這里x是常數(shù) (6)對(duì)于任意固定的常數(shù)x0和y0，logxn是O(ny,76,例：2n3+4n2logn=O(n3) 證明：logn=O(n) 規(guī)則6 4n2logn=O(4n3) 規(guī)則3 2n3+4n2logn=O(2n3+4n3) 規(guī)則2 2n3+4n3=O(n3) 規(guī)則1、多項(xiàng)式定理 2n3+4n2logn=O(n3,77,4）o,記號(hào),定義1.4 o記號(hào) 形式1：對(duì)任意正常數(shù)c，存在常數(shù)n00，使對(duì)所有的nn0，有|f(n)|

40、 c|g(n)|，則記作：f(n) = o(g(n)。 形式2：若 則記f(n) = o(g(n)。 例：2n = o(n2)，但2n2 o(n2,78,O和o的區(qū)別,O： o： 在o表示中，當(dāng)n趨于無窮時(shí)，f(n)相對(duì)于g(n)來說已經(jīng)不重要了,79,定義1.5 記號(hào) 形式1：對(duì)任意正常數(shù)c，存在常數(shù)n00，使對(duì)所有的nn0，有c|g(n)|f(n)| ，則記作： f(n) = (g(n)。 形式2：若 則記f(n) = o(g(n)。 例：n2/2 = (n)，但n2/2 (n2,80,和的區(qū)別,： ： 在表示中，當(dāng)n趨于無窮時(shí)，f(n)相對(duì)于g(n)來說變得任意大了,81,1.4 分析結(jié)論的證明,當(dāng)我們有了分析的結(jié)論，怎么證明結(jié)論是正確的？ 常用的方法： 直接推導(dǎo)（略） 數(shù)學(xué)歸納法 反證法 反例法,82