算法設(shè)計(jì)與分析演示

（優(yōu)選）算法設(shè)計(jì)與分析課件目前一頁\總數(shù)九十八頁\編于十六點(diǎn)寫在講課前一、什么是算法算法就是計(jì)算的方法。數(shù)·學(xué)數(shù)：1，2，3，4，…學(xué)：偶數(shù)、質(zhì)數(shù)、微積分…之?dāng)?shù)的學(xué)問算·法算：加、減、乘、除法：何時(shí)、何處用何計(jì)算之算的方法目前二頁\總數(shù)九十八頁\編于十六點(diǎn)寫在講課前（續(xù)）舉個(gè)例子：排序問題描述：將一組數(shù)按從小到大的順序整理有序基本思想：小的數(shù)往前排，大的數(shù)往后排怎么排？算法冒泡排序選擇排序歸并排序快速排序堆排序Shell排序…每種算法都是一組特定的規(guī)則，規(guī)定了一種處理數(shù)據(jù)的運(yùn)算方法目前三頁\總數(shù)九十八頁\編于十六點(diǎn)問題：既然每種方法都可以實(shí)現(xiàn)排序之目的，何必費(fèi)心研究這么多排序算法？其一：就像玩智力游戲，人們樂衷于尋找不同的方法解決各種各樣的問題。其二：研究的需要，算法和算法間是有區(qū)別的，我們有必要去研究，去分析。性質(zhì)不同：穩(wěn)定、不穩(wěn)定性能不同：速度、空間適用場(chǎng)合不同其三，應(yīng)用的需求，問題有千百萬種，沒有萬能的算法適合所有的應(yīng)用。需要我們找出算法的設(shè)計(jì)規(guī)律，并設(shè)計(jì)出解決問題的新算法怎么選擇：根據(jù)性能、結(jié)合需求、綜合選擇

如何了解每種算法的性能？算法的分析目前四頁\總數(shù)九十八頁\編于十六點(diǎn)二、算法分析了解算法的性能：算法速度：快還是慢？如何衡量？怎么比較？空間使用量(計(jì)算機(jī)算法*)：大還是小？如何衡量？怎么比較？其它方面的性質(zhì)等。目前五頁\總數(shù)九十八頁\編于十六點(diǎn)實(shí)例分析：排序算法的理論分析：（略）編程序測(cè)試1.冒泡排序真的很慢嗎？

數(shù)據(jù)集元素個(gè)數(shù)：10、20、1000、10000…2.快速和歸并排序都是O(nlogn)的時(shí)間復(fù)雜度，到底誰更快一點(diǎn)呢？原因是什么？3.冒泡排序會(huì)不會(huì)比快速排序快？來自于實(shí)測(cè)的結(jié)論：可能。目前六頁\總數(shù)九十八頁\編于十六點(diǎn)三、為什么要學(xué)習(xí)算法1.編程序的需要

任何程序都需要算法。thecoreofcomputerscience

程序=數(shù)據(jù)結(jié)構(gòu)+算法2.改造世界的需要

世界上還有很多很多的問題等待你解決，有無數(shù)的程序等待你去編。3.國家綜合實(shí)力的體現(xiàn)（大）從軟實(shí)力的角度，算法是國家科技生產(chǎn)力的核心。是國家綜合實(shí)力的體現(xiàn)。目前七頁\總數(shù)九十八頁\編于十六點(diǎn)四、頭疼的事：算法太多了，學(xué)不過來

是的，千萬的問題、萬千的算法。都學(xué)過來是不可能的。甚至專一門已經(jīng)很了不起。學(xué)習(xí)算法設(shè)計(jì)與分析的策略、技術(shù)和方法，把握解決問題的規(guī)律，為設(shè)計(jì)更復(fù)雜、更有效的算法奠定基礎(chǔ)。需要同學(xué)們不斷學(xué)習(xí)，深入思考，創(chuàng)新設(shè)計(jì)。目前八頁\總數(shù)九十八頁\編于十六點(diǎn)五、算法的學(xué)習(xí)過程：痛苦并快樂著1.枯燥的過程繁&煩：學(xué)習(xí)一個(gè)算法如同做一道數(shù)學(xué)題，多了呢？ACMICPC的訓(xùn)練過程：樂于其中2.智慧的積累方法的掌握、技術(shù)的升華3.理論的貢獻(xiàn)算法成就或在于理論的貢獻(xiàn)，而不僅僅是技術(shù)的提高。如何成就好算法：好思想+好技術(shù)目前九頁\總數(shù)九十八頁\編于十六點(diǎn)六、好算法從理論的角度說，好算法應(yīng)該有較低的時(shí)間復(fù)雜度（高速）和空間復(fù)雜度（低耗），但好的算法還要依靠好的算法實(shí)現(xiàn)，需要理論與技術(shù)、技巧的結(jié)合才能最終實(shí)現(xiàn)好的算法。從應(yīng)用的角度說，能有效地解決問題的算法都是好算法——不管黑貓白貓，抓住老鼠就是好貓；不管A算法、B算法，能解決問題就是好算法（實(shí)用了點(diǎn)）。目前十頁\總數(shù)九十八頁\編于十六點(diǎn)概述課程核心：

介紹算法設(shè)計(jì)與分析的基本理論、方法和技術(shù)，奠定算法設(shè)計(jì)的基礎(chǔ)。教學(xué)目的：在理論學(xué)習(xí)上，掌握算法分析與設(shè)計(jì)的基本理論和方法，培養(yǎng)設(shè)計(jì)新算法和分析算法復(fù)雜性的能力。在實(shí)踐教學(xué)上，掌握算法實(shí)現(xiàn)的技術(shù)、技巧，學(xué)習(xí)算法的正確性驗(yàn)證、效率分析、優(yōu)化技術(shù)，以及算法在實(shí)際問題中的應(yīng)用。培養(yǎng)獨(dú)立研究和創(chuàng)新能力。目前十一頁\總數(shù)九十八頁\編于十六點(diǎn)課程內(nèi)容：基本概念：算法的定義、性質(zhì)、

分析算法的基本方法等分治策略（Divideandconquer）貪心方法（Greedymethod）動(dòng)態(tài)規(guī)劃（DynamicProgramming）圖算法（GraphAlgorithms）回溯與分枝限界……專題綜合實(shí)踐目前十二頁\總數(shù)九十八頁\編于十六點(diǎn)本課程需要的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)語言（C/C++）：結(jié)構(gòu)化設(shè)計(jì)數(shù)學(xué)基礎(chǔ)

操作系統(tǒng)、編譯

目前十三頁\總數(shù)九十八頁\編于十六點(diǎn)授課形式:課堂教學(xué)：（√）課堂討論：專題、解題報(bào)告上機(jī)實(shí)踐：需要提交實(shí)驗(yàn)報(bào)告目前十四頁\總數(shù)九十八頁\編于十六點(diǎn)考核方式:考試：（√）綜合成績(jī)=卷面成績(jī)*80%+平時(shí)成績(jī)*20%平時(shí)成績(jī)=作業(yè)+上機(jī)實(shí)驗(yàn)+考勤目前十五頁\總數(shù)九十八頁\編于十六點(diǎn)主要參考書計(jì)算機(jī)算法基礎(chǔ)，

余祥宣等編著，

華中科技大學(xué)出版社Introductiontoalgorithms,ThomasH.Cormen,etc.,thirdedition,TheMITPress.AlgorithmDesign，MichaelT.Goodrich算法設(shè)計(jì)與分析，王曉東，清華大學(xué)出版社目前十六頁\總數(shù)九十八頁\編于十六點(diǎn)其它參考書TheArtofComputerProgramming,DonaldE.Knuth.Volume1-3,SecondEdition.DataStructures,Algorithms,andApplicationsinC++(Part3)SartajSahni,ChinaMachinePressetc.目前十七頁\總數(shù)九十八頁\編于十六點(diǎn)一、算法基礎(chǔ)參考資料：《計(jì)算機(jī)算法基礎(chǔ)》

第二章

《Introductiontoalgorithms》Chapter1、Chapter3目前十八頁\總數(shù)九十八頁\編于十六點(diǎn)1.1算法的定義及特性1.什么是算法？如數(shù)字、計(jì)算一樣，算法是一個(gè)基本概念。算法是解一確定類問題的任意一種特殊的方法。在計(jì)算機(jī)科學(xué)中，算法是使用計(jì)算機(jī)解一類問題的精確、有效方法的代名詞；

算法是一組有窮的規(guī)則，它規(guī)定了解決某一特定類型問題的一系列運(yùn)算。目前十九頁\總數(shù)九十八頁\編于十六點(diǎn)對(duì)算法概念的理解算法由運(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í)間有限目前二十頁\總數(shù)九十八頁\編于十六點(diǎn)我們已經(jīng)接觸過的算法：分類（排序）算法：將已知的n個(gè)元素按照關(guān)鍵值大小的非增/非降順序重新排列。如：冒泡排序、插入排序、歸并排序查找算法：從已知的元素集合中找出滿足要求的一個(gè)或一組元素。如：順序查找、二分查找、第k小元素圖算法：在已知的圖中找出滿足某些性質(zhì)的結(jié)點(diǎn)或邊。如：最短路徑算法、最小成本生成樹目前二十一頁\總數(shù)九十八頁\編于十六點(diǎn)思考：我們學(xué)會(huì)了解決一個(gè)個(gè)具體問題的算法，那么在這些算法的設(shè)計(jì)中有沒有一些共性的東西？有沒有可以總結(jié)出來的規(guī)律、規(guī)則和方法？這些規(guī)律、規(guī)則和方法對(duì)于其它算法的設(shè)計(jì)有沒有指導(dǎo)意義？能不能找到一些算法設(shè)計(jì)的一般策略、技術(shù)和方法？目前二十二頁\總數(shù)九十八頁\編于十六點(diǎn)算法：求解問題的一組規(guī)則檢索問題分治策略排序問題貪心策略路徑問題規(guī)則的設(shè)計(jì)設(shè)計(jì)策略動(dòng)態(tài)規(guī)劃最優(yōu)化問題檢索遍歷問題回溯…分枝限界….發(fā)現(xiàn)指導(dǎo)形成算法產(chǎn)生算法設(shè)計(jì)的指導(dǎo)思想和基本規(guī)律目前二十三頁\總數(shù)九十八頁\編于十六點(diǎn)較高的算法設(shè)計(jì)能力不僅在于簡(jiǎn)單地使用一些具體的算法，更在于對(duì)算法設(shè)計(jì)方法的掌握上。只有深入理解算法設(shè)計(jì)的策略、技術(shù)和方法，才能在面對(duì)新問題時(shí)創(chuàng)造出新的算法。算法學(xué)習(xí)要做到：深入理解算法設(shè)計(jì)的一般規(guī)律、技術(shù)和方法靈活運(yùn)用現(xiàn)有的算法解決實(shí)際問題在改造客觀世界的過程中，運(yùn)用學(xué)到的知識(shí)創(chuàng)造新的算法，解決新的問題目前二十四頁\總數(shù)九十八頁\編于十六點(diǎn)2.算法的五個(gè)重要特性確定性、能行性、輸入、輸出、有窮性1）確定性：算法使用的每種運(yùn)算必須要有確切的定義，不能有二義性。例：不符合確定性的運(yùn)算5/0將6或7與x相加未賦值變量參與運(yùn)算目前二十五頁\總數(shù)九十八頁\編于十六點(diǎn)2）能行性算法中有待實(shí)現(xiàn)的運(yùn)算都是基本的運(yùn)算，原理上每種運(yùn)算都能由人用紙和筆在“有限”的時(shí)間內(nèi)完成。例：整數(shù)的算術(shù)運(yùn)算是“能行”的實(shí)數(shù)的算術(shù)運(yùn)算可能是“不能行”的目前二十六頁\總數(shù)九十八頁\編于十六點(diǎn)如何認(rèn)識(shí)算法的確定性和能行性？確定性和能行性是算法設(shè)計(jì)過程可能存在的問題。一個(gè)實(shí)際的程序設(shè)計(jì)語言定義了該語言中可以使用的數(shù)據(jù)類型和能夠參與的運(yùn)算，編譯器可以對(duì)程序中的非法運(yùn)算檢錯(cuò)。非確定、非能行的“臆造”運(yùn)算是不能存在的，程序的正確性主要在于邏輯正確。但算法本身的正確性不僅在于此。目前二十七頁\總數(shù)九十八頁\編于十六點(diǎn)3）輸入每個(gè)算法都有0個(gè)或多個(gè)輸入。這些輸入是在算法開始之前給出的量，取自于特定的對(duì)象集合——定義域4）輸出一個(gè)算法產(chǎn)生一個(gè)或多個(gè)輸出，這些輸出是同輸入有某種特定關(guān)系的量。目前二十八頁\總數(shù)九十八頁\編于十六點(diǎn)算法的狀態(tài)轉(zhuǎn)換算法：把特定的輸入轉(zhuǎn)換成需要的輸出。算法輸入輸出狀態(tài)：算法/程序中一組變量的當(dāng)前值稱為算

法/程序的當(dāng)前狀態(tài)。算法：狀態(tài)轉(zhuǎn)換器，算法把輸入時(shí)的初始狀態(tài)

轉(zhuǎn)換為輸出時(shí)的終止?fàn)顟B(tài)目前二十九頁\總數(shù)九十八頁\編于十六點(diǎn)5）有窮性一個(gè)算法總是在執(zhí)行了有窮步的運(yùn)算之后終止。計(jì)算過程：滿足確定性、能行性、輸入、輸出，但不一定滿足有窮性的一組規(guī)則。算法和計(jì)算過程的關(guān)系：計(jì)算過程：操作系統(tǒng)(不終止的運(yùn)行過程)

算法是“可以終止的計(jì)算過程”目前三十頁\總數(shù)九十八頁\編于十六點(diǎn)時(shí)效性：實(shí)際問題往往都有時(shí)間要求。例：國際象棋（啟發(fā)）數(shù)值天氣預(yù)報(bào)

只有在要求的時(shí)間內(nèi)解決問題才是有意義的。目前三十一頁\總數(shù)九十八頁\編于十六點(diǎn)

針對(duì)算法的時(shí)效性，只有把在相當(dāng)有窮步內(nèi)終止的算法投入到計(jì)算機(jī)上運(yùn)行才是實(shí)際可行的。何為“相當(dāng)有窮”？

——通過算法分析，了解算法速度，給出算法計(jì)算時(shí)間的一個(gè)精確的描述，以衡量算法的執(zhí)行速度，選擇合適的算法解決問題。

注：算法分析還包括空間分析。目前三十二頁\總數(shù)九十八頁\編于十六點(diǎn)與算法學(xué)習(xí)相關(guān)的內(nèi)容五個(gè)方面：設(shè)計(jì)、表示、證明、分析、測(cè)試1）設(shè)計(jì)：構(gòu)思算法的處理規(guī)則，創(chuàng)造性的活動(dòng)。2）表示：用語言把算法描述出來。類計(jì)算機(jī)語言、偽代碼

（SPARKS語言、類C語言）、流程圖、自然語言等3）證明：證明算法的正確性。正確性：對(duì)合法輸入能得出正確的答案。

算法證明：證明算法的正確性，與語言無關(guān)程序證明：證明程序的正確性(理論證明，程序邏輯)

目前三十三頁\總數(shù)九十八頁\編于十六點(diǎn)一個(gè)例子：插入分類輸入：n個(gè)元素存放在數(shù)組A中：A[1]~A[n]，無序輸出：按照從小到大的順序重新整理的有序數(shù)組A插入分類算法的設(shè)計(jì)思想：1.將第一個(gè)元素（A[1]）看作只有一個(gè)元素的有序子序列；2.置循環(huán)i=2ton，將A[i]插入到由A[1]~A[i-1]元素組成的有序子序列中。思考問題：上述設(shè)計(jì)思路對(duì)嗎？如何實(shí)現(xiàn)？

目前三十四頁\總數(shù)九十八頁\編于十六點(diǎn)SPARKS語言算法描述：

procedureINSERTIONSORT(A,n)A(0)←-∞//A[0]做監(jiān)視哨fori←2tondo//從第二個(gè)元素開始循環(huán)item←A(i);//將A[i]放到臨時(shí)變量item中

j←i-1//從后往前查找當(dāng)前元素的插入位置whileitem<A(j)doA(j+1)←A(j);//比item大的元素往后移一位

j←j-1;//繼續(xù)往前查找repeatA(j+1)←item;//將item插入到正確的位置上repeatendINSERTIONSORT

目前三十五頁\總數(shù)九十八頁\編于十六點(diǎn)算法導(dǎo)論算法描述：INSERTIONSORT(A,n)A[0]←-∞▽A[0]做監(jiān)視哨fori←2ton▽從第二個(gè)元素開始循環(huán)doitem←A[i]▽將A[i]放到臨時(shí)變量item中

j←i-1▽從后往前查找當(dāng)前元素的插入位置whileitem<A[j]doA[j+1]←A[j]▽比item大的元素往后移一位

j←j-1;▽繼續(xù)往前查找A(j+1)←item;▽將item插入到正確的位置上

目前三十六頁\總數(shù)九十八頁\編于十六點(diǎn)基于上述算法，思考：這個(gè)算法描述正確嗎？

能行、確定、輸入、輸出、有窮？

正確性證明運(yùn)算得快嗎？時(shí)間復(fù)雜度分析使用了多少內(nèi)存？空間復(fù)雜度分析進(jìn)一步我們需要回答：它能夠應(yīng)用到那些領(lǐng)域？要做深入進(jìn)一步分析利用不同語言實(shí)現(xiàn)需要那些技巧?實(shí)現(xiàn)目前三十七頁\總數(shù)九十八頁\編于十六點(diǎn)4）分析：對(duì)算法的時(shí)、空特性做定性、定量分析，以了解算法的性質(zhì)。5）測(cè)試：將算法變成程序，放到計(jì)算機(jī)上運(yùn)行，觀察運(yùn)行情況編程中的調(diào)試：排錯(cuò)過程?！罢{(diào)試只能指出有錯(cuò)誤，而不能指出它們不存在錯(cuò)誤”——Dijkstra的名言運(yùn)行中的測(cè)試：分析過程。作時(shí)空分布圖，驗(yàn)證分析結(jié)論，進(jìn)一步優(yōu)化算法的設(shè)計(jì)。本課程集中于學(xué)習(xí)算法的設(shè)計(jì)與分析。通過學(xué)習(xí)，掌握計(jì)算機(jī)算法設(shè)計(jì)和分析基本策略與方法，為設(shè)計(jì)更復(fù)雜、更有效的算法奠定基礎(chǔ)目前三十八頁\總數(shù)九十八頁\編于十六點(diǎn)1.分析算法的目的?算法選擇的需要：對(duì)同一個(gè)問題可以設(shè)計(jì)不同的算法，不同算法的時(shí)間和空間特性是不同的

?算法優(yōu)化的需要：有沒有可以改進(jìn)的地方，以使算法工作得更好？分析算法的目的在于：通過對(duì)算法的分析了解算法的性能，1）可以在解決同一問題的不同算法之間比較性能的好壞，從而運(yùn)行好的算法，改進(jìn)差的算法，避免無益的人力和物力浪費(fèi)。2）可以對(duì)算法的性質(zhì)作深入了解，從而可以進(jìn)一步優(yōu)化算法，讓其更好地工作。1.2分析算法基礎(chǔ)目前三十九頁\總數(shù)九十八頁\編于十六點(diǎn)2.重要的假設(shè)和約定1）計(jì)算機(jī)模型的假設(shè)計(jì)算機(jī)形式理論模型：有限狀態(tài)自動(dòng)機(jī)、Turing機(jī)通用的順序計(jì)算機(jī)模型：?jiǎn)蜟PU——串行算法有足夠的“內(nèi)存”，并能在固定的時(shí)間內(nèi)存取數(shù)據(jù)單元

RAM——random-accessmachine區(qū)分計(jì)算機(jī)的理論模型與實(shí)際的計(jì)算機(jī)目前四十頁\總數(shù)九十八頁\編于十六點(diǎn)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又是多少?目前四十一頁\總數(shù)九十八頁\編于十六點(diǎn)運(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)算、過程調(diào)用等特點(diǎn)：執(zhí)行時(shí)間是固定量，與具體的操作數(shù)無關(guān)。

例：1+1=2vs10000+10000=20000100*100=10000vs10000*10000=100000000CALLINSERTIONSORT目前四十二頁\總數(shù)九十八頁\編于十六點(diǎn)更一般的情況設(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í)間t0即可完成的運(yùn)算——稱具有這種性質(zhì)的運(yùn)算為時(shí)間囿界于常數(shù)的運(yùn)算。目前四十三頁\總數(shù)九十八頁\編于十六點(diǎn)運(yùn)算的分類（續(xù)）

時(shí)間非囿界于常數(shù)的運(yùn)算：字符串操作：與字符串中字符的數(shù)量成正比例：字符串的比較運(yùn)算（strcmp）記錄操作：與記錄的屬性數(shù)、屬性類型等有關(guān)特點(diǎn)：運(yùn)算時(shí)間與操作數(shù)相關(guān)，每次執(zhí)行的時(shí)間是一個(gè)不定的量。

目前四十四頁\總數(shù)九十八頁\編于十六點(diǎn)怎么分析時(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

=Length（String）*tchar故：分析時(shí)間非囿界于常數(shù)的運(yùn)算時(shí)，只需將其分解成若干時(shí)間囿界于常數(shù)的運(yùn)算即可。目前四十五頁\總數(shù)九十八頁\編于十六點(diǎn)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)的工作情況。目前四十六頁\總數(shù)九十八頁\編于十六點(diǎn)注：編制測(cè)試數(shù)據(jù)對(duì)算法分析與程序調(diào)試都是關(guān)鍵的，但目的不同。算法分析數(shù)據(jù)集：反映算法的典型執(zhí)行情況（最好、最壞、平均）；調(diào)試程序數(shù)據(jù)集：排錯(cuò)。力求走到程序的每個(gè)分支，驗(yàn)證各種情況下程序執(zhí)行正確與否。目前四十七頁\總數(shù)九十八頁\編于十六點(diǎn)3.如何進(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)。目前四十八頁\總數(shù)九十八頁\編于十六點(diǎn)事后測(cè)試：將算法編制成程序，放到實(shí)際的計(jì)算機(jī)上運(yùn)行，收集程序的執(zhí)行時(shí)間和空間占用情況等統(tǒng)計(jì)數(shù)據(jù)，然后進(jìn)行分析判斷。事后測(cè)試與物理實(shí)現(xiàn)直接有關(guān)。

算法分析主要集中于與物理實(shí)現(xiàn)無關(guān)的事前分析階段——獲取算法的理論時(shí)間/空間復(fù)雜度。目前四十九頁\總數(shù)九十八頁\編于十六點(diǎn)1）事前分析目標(biāo)：獲取算法的時(shí)間（空間）復(fù)雜度函數(shù)，從理論上分析算法性能的好壞。可以分為時(shí)間、空間兩個(gè)方面：時(shí)間分析：了解算法中使用了哪些運(yùn)算(主要是具有單位執(zhí)行時(shí)間的基本運(yùn)算)。分析程序的控制流程，從而確定各類運(yùn)算的執(zhí)行次數(shù)。將對(duì)運(yùn)算執(zhí)行次數(shù)的統(tǒng)計(jì)分析結(jié)果表示成關(guān)于問題規(guī)模n的特征函數(shù)。算法性能有最好、平均、最壞等情況，與數(shù)據(jù)配置有關(guān)。分析典型的數(shù)據(jù)配置，了解算法在各種情況下的執(zhí)行情況。目前五十頁\總數(shù)九十八頁\編于十六點(diǎn)空間分析：分析算法中各類變量的定義情況和使用情況將空間占用量表示成為問題規(guī)模n的特征函數(shù)?？臻g占用有最大、平均、最少等情況，與數(shù)據(jù)配置有關(guān)。分析典型的數(shù)據(jù)配置，了解算法在各種情況下的空間占用情況。目前五十一頁\總數(shù)九十八頁\編于十六點(diǎn)如何進(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ù)等，它們的一次執(zhí)行時(shí)間也可視為常量、單位時(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)用等。目前五十二頁\總數(shù)九十八頁\編于十六點(diǎn)

例：執(zhí)行次數(shù)的統(tǒng)計(jì)

x←x+yfori←1tondofori←1tondox←x+yforj←1tondorepeatx←x+yrepeatrepeat(a)(b)(c)

分析：

(a)：x←x+y執(zhí)行了1次

(b)：x←x+y執(zhí)行了n次

(c)：x←x+y執(zhí)行了n2次fori←1tondoforj←itondox←x+yrepeatrepeat(d)目前五十三頁\總數(shù)九十八頁\編于十六點(diǎn)（二）將頻率計(jì)數(shù)表示成問題規(guī)模n的函數(shù)：

如：an2+bn+c★

算法的執(zhí)行時(shí)間是算法中各類運(yùn)算執(zhí)行時(shí)間之和，將正比于各類運(yùn)算的頻率計(jì)數(shù)之和。★事前分析的頻率計(jì)數(shù)結(jié)果與所使用的機(jī)器及其他環(huán)境因素?zé)o關(guān)（如程序設(shè)計(jì)語言、編譯器），只與算法本身的控制流程有關(guān)。目前五十四頁\總數(shù)九十八頁\編于十六點(diǎn)例：插入分類

procedureINSERTIONSORT(A,n)//將A(1：n)中的元素按非降次序分類，n≥1//執(zhí)行次數(shù)單位執(zhí)行時(shí)間

A(0)←-∞//設(shè)置初始邊界值1t1forj←2tondo//A(1:j-1)已分類//n-1t2item←A(j);n-1t3

i←j-1n-1t4

whileitem<A(i)do//0≤i<j//最多i次,最少1次t5A(i+1)←A(i);最多i-1次,最少0次t6i←i-1;最多i-1次,最少0次t4repeatA(i+1)←item;n-1次t7repeatendINSERTIONSORT目前五十五頁\總數(shù)九十八頁\編于十六點(diǎn)

令t0=max(t1,t2,t3,t4,t5,t6,t7)，則最壞情況（逆序）最好情況（正序）目前五十六頁\總數(shù)九十八頁\編于十六點(diǎn)進(jìn)一步的分析：主要針對(duì)算法最主要的部分進(jìn)行分析，抓住主要矛盾即可，如插入排序中,可以僅集中于對(duì)for/while雙重嵌套循環(huán)的分析，而忽略順序或執(zhí)行次數(shù)較低的部分。（三）函數(shù)表達(dá)式的數(shù)量級(jí)（階）函數(shù)表達(dá)式中的最高次項(xiàng)的次數(shù)，稱為函數(shù)表達(dá)式的數(shù)量級(jí)，是衡量頻率計(jì)數(shù)的“大小”的一種測(cè)度。目前五十七頁\總數(shù)九十八頁\編于十六點(diǎn)數(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í)間——與環(huán)境因素?zé)o關(guān)。實(shí)例：工資的級(jí)別（定性的表示）目前五十八頁\總數(shù)九十八頁\編于十六點(diǎn)（四）限界函數(shù)

一般用頻率計(jì)數(shù)函數(shù)表達(dá)式中的最高次項(xiàng)表示算法復(fù)雜性分析的最終結(jié)果——限界函數(shù)，且忽略掉其系數(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í)間特性的分析類似，略）目前五十九頁\總數(shù)九十八頁\編于十六點(diǎn)2）事后測(cè)試把算法編制成程序，在實(shí)際的計(jì)算機(jī)硬件平臺(tái)上運(yùn)行程序，統(tǒng)計(jì)執(zhí)行中實(shí)際耗費(fèi)的時(shí)間與空間，與事前分析的結(jié)論進(jìn)行比較，驗(yàn)證先前的分析結(jié)論是否正確，并優(yōu)化所設(shè)計(jì)的算法。分析手段：作時(shí)、空性能分布圖目前六十頁\總數(shù)九十八頁\編于十六點(diǎn)4.計(jì)算時(shí)間的漸近表示——Ο、Ω、Θ的定義

算法時(shí)間/空間復(fù)雜度的限界函數(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)。

目前六十一頁\總數(shù)九十八頁\編于十六點(diǎn)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倍，除非n<n0。即是說，當(dāng)n充分大時(shí)，g是f的一個(gè)上界函數(shù)（在一個(gè)非零常數(shù)倍的意義下）。這時(shí)候也稱f(n)的數(shù)量級(jí)就是g(n)。目前六十二頁\總數(shù)九十八頁\編于十六點(diǎn)

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ù)，可看作n04n+3=O(n)：可取c＝5，n0＝3100n+6=O(n)：可取c=101，n0＝66×2n+n2=O(2n)：可取c=7，n0=410n2+4n+3=O(n2)3logn+2n+n2=O(n2)nlogn+n2=O(n2)目前六十三頁\總數(shù)九十八頁\編于十六點(diǎn)注：1．總是試圖求出數(shù)量級(jí)最小的g(n)作為f(n)的上界函數(shù)，即，

g(n)應(yīng)該盡量接近函數(shù)f(n)。數(shù)量級(jí)越小，限界越精確。

如

若：3n+2=O(n2)則是松散的界限；

而：3n+2=O(n)就是較緊的界限。2．不要產(chǎn)生錯(cuò)誤界限。

如，n2+100n+6，當(dāng)n<3時(shí)，n2+100n+6<106n，

由此就認(rèn)為n2+100n+6＝O(n)是錯(cuò)誤的。

事實(shí)上，對(duì)任何正的常數(shù)c，只要n>c-100就有n2+100n+6>c×n。

提示：注意大系數(shù)低次項(xiàng)的影響

同理，3n2+4×2n=O(n)也是錯(cuò)誤的。目前六十四頁\總數(shù)九十八頁\編于十六點(diǎn)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和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)容參見《IntruductiontoAlgorithm》Chapter3，Ω、Θ相同）

目前六十五頁\總數(shù)九十八頁\編于十六點(diǎn)

[定理1.1大O比率定理]對(duì)于函數(shù)f(n)和g(n)，若

存在，則f(n)=O(g(n))，當(dāng)且僅當(dāng)存在確定的常數(shù)c，有

≤c。證明：1）如果f(n)=O(g(n))，則存在c>0及某個(gè)n0，使得對(duì)于所有的n≥n0，有f(n)/g(n)≤c，因此≤c。2）假定≤c，它表明存在一個(gè)n0，使得對(duì)于所有的n≥n0，有f(n)≤max{1,c}*g(n)。證畢。目前六十六頁\總數(shù)九十八頁\編于十六點(diǎn)例：因?yàn)椋?n+2=O(n)因?yàn)?，所?n2+5n+2=O(n2)因?yàn)?，所?×2n+n2=O(2n)考察下式：因?yàn)?，所以n9+3n2=O(2n)，是否合適？顯然這不是一個(gè)好的上界估計(jì)。原因在于：極限值不是一個(gè)正常數(shù)（見O的定義）。目前六十七頁\總數(shù)九十八頁\編于十六點(diǎn)用于估算復(fù)雜性階的定理[定理1.2]對(duì)于任意正實(shí)數(shù)x和ε，有下面的不等式：1)存在某個(gè)n0,使得對(duì)于任何n≥n0,有(logn)x<(logn)x+ε2)存在某個(gè)n0,使得對(duì)于任何n≥n0

，有(logn)x<n。3)存在某個(gè)n0,使得對(duì)于任何n≥n0，有nx<nx+ε。4)存在某個(gè)n0,使得對(duì)于任何n≥n0

，有nx<2n。5)對(duì)任意實(shí)數(shù)y,存在某個(gè)n0，使得對(duì)于任何n≥n0，有

nx(logn)y<nx+ε目前六十八頁\總數(shù)九十八頁\編于十六點(diǎn)例:

根據(jù)定理1.2，很容易得出：n3+n2logn=O(n3)；n4+n2.5log20n=O(n4)；2nn4log3n＋2nn5/log3n=O(2nn5)。目前六十九頁\總數(shù)九十八頁\編于十六點(diǎn)定義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

。即是說，當(dāng)n充分大時(shí)，g是f的一個(gè)下界函數(shù)（在一個(gè)非零常數(shù)倍的意義下）。目前七十頁\總數(shù)九十八頁\編于十六點(diǎn)注：1.通常情況下，下界函數(shù)也取單項(xiàng)的形式。2.總是試圖求出數(shù)量級(jí)最大的g(n)作為f(n)的下界函數(shù)，g(n)應(yīng)該盡量接近函數(shù)f(n)。3.類似于大O符號(hào)，可以參考定理1.2所列的不等式，來估計(jì)復(fù)雜性函數(shù)的下界。其它具有和大O類似的性質(zhì)。目前七十一頁\總數(shù)九十八頁\編于十六點(diǎn)

[定理1.3大Ω比率定理]對(duì)于函數(shù)f(n)和g(n)，若

存在，則f(n)=Ω(g(n))，當(dāng)且僅當(dāng)存在確定的常數(shù)c，有

≤c。注：這里，當(dāng)n充分大時(shí)，g(n)≤cf(n)意味著，

由此不難看出上述判別規(guī)則的正確性。目前七十二頁\總數(shù)九十八頁\編于十六點(diǎn)定義1.3（“平均情況”）

如果存在正常數(shù)c1，c2和n0，對(duì)于所有的n≥n0，有c1|g(n)|≤|f(n)|≤c2|g(n)|，

則記作含義：算法在最好和最壞情況下的計(jì)算時(shí)間就一個(gè)常數(shù)因子范圍內(nèi)而言是相同的?？煽醋鳎杭扔衒(n)=Ω(g(n))，又有f(n)=Ο(g(n))函數(shù)f介于函數(shù)g的c1和c2倍之間，即當(dāng)n充分大時(shí)，g既是f的下界，又是f的上界。目前七十三頁\總數(shù)九十八頁\編于十六點(diǎn)

[定理1.4大Θ比率定理]對(duì)于函數(shù)f(n)和g(n)，若

和

都存在，則f(n)=

Θ(g(n))，當(dāng)且僅當(dāng)存在確定的常數(shù)c1和c2，有

≤c1和≤c2。目前七十四頁\總數(shù)九十八頁\編于十六點(diǎn)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：分別需要1048576和10240次運(yùn)算。

n=2048：分別需要4194304和22528次運(yùn)算?？梢钥吹剑骸锿纫?guī)模n=1024下，計(jì)算量有近百倍的差距；★而在規(guī)模加倍后，一個(gè)Ο(n2)的算法計(jì)算時(shí)間增長(zhǎng)4倍，而一個(gè)Ο(nlogn)算法則只增長(zhǎng)一倍多一點(diǎn)。目前七十五頁\總數(shù)九十八頁\編于十六點(diǎn)（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)<Ο(n2)<Ο(n3)指數(shù)時(shí)間算法：計(jì)算時(shí)間用指數(shù)函數(shù)限界的算法。常見的

指數(shù)時(shí)間限界函數(shù)：

Ο(2n)<Ο(n！)<Ο(nn)復(fù)雜性越來越高復(fù)雜性越來越高目前七十六頁\總數(shù)九十八頁\編于十六點(diǎn)當(dāng)n取值較大時(shí)，指數(shù)時(shí)間算法和多項(xiàng)式時(shí)間算法在計(jì)算時(shí)間上非常懸殊。計(jì)算時(shí)間的典型函數(shù)曲線目前七十七頁\總數(shù)九十八頁\編于十六點(diǎn)計(jì)算時(shí)間函數(shù)值比較lognnnlognn2n32n010112122484248166416382464512256416642564096655365321601024327684294967296表1.1典型函數(shù)的值目前七十八頁\總數(shù)九十八頁\編于十六點(diǎn)對(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ò)大所處理問題的規(guī)模，有效的途徑是降低算法的計(jì)算復(fù)雜度，而不是（僅僅依靠）提高計(jì)算機(jī)的速度。目前七十九頁\總數(shù)九十八頁\編于十六點(diǎn)NP問題：Non-deterministicPolynomial，多項(xiàng)式復(fù)雜程度的非確定性問題。什么是非確定性問題呢？

有些計(jì)算問題是確定性的，比如加減乘除之類，只要按照公式推導(dǎo)，按部就班一步步來，就可以得到結(jié)果。但是，有些問題是無法按部就班直接地計(jì)算出來。比如，找大質(zhì)數(shù)的問題。有沒有一個(gè)公式就可以一步步推算出來，下一個(gè)質(zhì)數(shù)應(yīng)該是多少呢？這樣的公式是沒有的。再比如，大的合數(shù)分解質(zhì)因數(shù)的問題，有沒有一個(gè)公式，把合數(shù)代進(jìn)去，就直接可以算出，它的因子各自是多少？也沒有這樣的公式。這種問題的答案，是無法直接計(jì)算得到的，只能通過間接的“猜算”來得到結(jié)果。這也就是非確定性問題。

但對(duì)這些問題通常有個(gè)算法，它不能直接告訴你答案是什么，但可以告訴你，某個(gè)可能的結(jié)果是正確的答案還是錯(cuò)誤的。這個(gè)可以告訴你“猜算”的答案正確與否的算法，假如可以在多項(xiàng)式時(shí)間內(nèi)算出來，就叫做多項(xiàng)式非確定性問題。而如果這個(gè)問題的所有可能答案，都是可以在多項(xiàng)式時(shí)間內(nèi)進(jìn)行正確與否的驗(yàn)算的話，就叫完全多項(xiàng)式非確定問題。完全多項(xiàng)式非確定性問題可以用窮舉法得到答案，一個(gè)個(gè)檢驗(yàn)下去，最終便能得到結(jié)果。但是這樣算法的復(fù)雜程度，是指數(shù)關(guān)系，因此計(jì)算的時(shí)間隨問題的復(fù)雜程度成指數(shù)的增長(zhǎng)，很快便變得不可計(jì)算了。目前八十頁\總數(shù)九十八頁\編于十六點(diǎn)（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)n≥n0時(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

。證畢。應(yīng)用：如果一個(gè)算法的復(fù)雜度函數(shù)是多項(xiàng)式形式，則其階函數(shù)就可取該多項(xiàng)式的最高次項(xiàng)。目前八十一頁\總數(shù)九十八頁\編于十六點(diǎn)3）

限界函數(shù)的性質(zhì)傳遞性：若且，則。（同）自反性：對(duì)稱性：若，則。轉(zhuǎn)置對(duì)稱性：當(dāng)且僅當(dāng)證明：從定義出發(fā)。

證明過程略。目前八十二頁\總數(shù)九十八頁\編于十六點(diǎn)定理：設(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(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)；目前八十三頁\總數(shù)九十八頁\編于十六點(diǎn)例：2n3+4n2logn=O(n3)證明：logn=O(n)規(guī)則64n2logn=O(4n3)規(guī)則3,乘法原理2n3+4n2logn=O(2n3+4n3)規(guī)則2,加法原理2n3+4n3=O(n3)規(guī)則1、多項(xiàng)式定理2n3+4n2logn=O(n3)目前八十四頁\總數(shù)九十八頁\編于十六點(diǎn)4）o,ω記號(hào)定義1.4o記號(hào)形式1：對(duì)任意正常數(shù)c，存在常數(shù)n0＞0，使對(duì)所有的n≥n0，有|f(n)|≤c|g(n)|，則記作：

f(n)=o(g(n))。形式2：若則記f(n)=o(g(n))。例：2n=o(n2)，但2n2≠o(n2)目前八十五頁\總數(shù)九十八頁\編于十六點(diǎn)O和o的區(qū)別O：o：在o表示中，當(dāng)n趨于無窮時(shí)，f(n)相對(duì)于g(