算法設計與分析(一)

1、算法設計與分析2013.4王多強華中科技大學計算機學院寫在講課前一、什么是算法算法就是計算的方法。u數學p數：1，2，3，4，p學：偶數、質數、微積分之數的學問 u算法p算：加、減、乘、除p法：何時、何處用何計算之算的方法寫在講課前（續(xù)）舉個例子：排序問題描述：將一組數按從小到大的順序整理有序基本思想：小的數往前排，大的數往后排怎么排？算法l冒泡排序l選擇排序l歸并排序l快速排序l堆排序lShell排序l每種算法都是一組特定的規(guī)則，規(guī)定了一種處理數據的運算方法問題：既然每種方法都可以實現(xiàn)排序之目的，何必費心研究這么多排序算法？其一：就像玩智力游戲，人們樂衷于尋找不同的方法解決各種各樣的問題。其

2、二：研究的需要，算法和算法間是有區(qū)別的，我們有必要去研究，去分析。l性質不同：穩(wěn)定、不穩(wěn)定l性能不同：速度、空間l適用場合不同其三，應用的需求，問題有千百萬種，沒有萬能的算法適合所有的應用。需要我們找出算法的設計規(guī)律，并設計出解決問題的新算法 怎么選擇：根據性能、結合需求、綜合選擇 如何了解每種算法的性能？算法的分析二、算法分析 了解算法的性能：l算法速度：快還是慢？如何衡量？怎么比較？l空間使用量(計算機算法*)：大還是??？如何衡量？怎么比較？l其它方面的性質等。實例分析：排序算法的理論分析：（略）編程序測試l1.冒泡排序真的很慢嗎？ 數據集元素個數：10、20、1000、10000l2.快

3、速和歸并排序都是O(nlogn)的時間復雜度， 到底誰更快一點呢？原因是什么？l3.冒泡排序會不會比快速排序快？ 來自于實測的結論：可能。三、為什么要學習算法1. 編程序的需要 任何程序都需要算法。 the core of computer science 程序 = 數據結構 + 算法2. 改造世界的需要 世界上還有很多很多的問題等待你解決，有無數的程序等待你去編。3. 國家綜合實力的體現(xiàn)（大） 從軟實力的角度，算法是國家科技生產力的核心。是國家綜合實力的體現(xiàn)。四、頭疼的事：算法太多了，學不過來 是的，千萬的問題、萬千的算法。都學過來是不可能的。甚至專一門已經很了不起。 學習算法設計與分析的策

4、略、技術和方法，把握解決問題的規(guī)律，為設計更復雜、更有效的算法奠定基礎。 需要同學們不斷學習，深入思考，創(chuàng)新設計。五、算法的學習過程：痛苦并快樂著1.枯燥的過程l繁&煩：學習一個算法如同做一道數學題，多了呢？lACM ICPC的訓練過程：樂于其中2.智慧的積累方法的掌握、技術的升華3.理論的貢獻l算法成就或在于理論的貢獻，而不僅僅是技術的提高。如何成就好算法：好思想+好技術六、好算法從理論的角度說，好算法應該有較低的時間復雜度（高速）和空間復雜度（低耗），但好的算法還要依靠好的算法實現(xiàn)，需要理論與技術、技巧的結合才能最終實現(xiàn)好的算法。從應用的角度說，能有效地解決問題的算法都是好算法不管

5、黑貓白貓，抓住老鼠就是好貓；不管A算法、B算法，能解決問題就是好算法（實用了點）。概述課程核心： 介紹算法設計與分析的基本理論、方法和技術，奠定算法設計的基礎。教學目的：l在理論學習上，掌握算法分析與設計的基本理論和方法，培養(yǎng)設計新算法和分析算法復雜性的能力。l在實踐教學上，掌握算法實現(xiàn)的技術、技巧，學習算法的正確性驗證、效率分析、優(yōu)化技術，以及算法在實際問題中的應用。l培養(yǎng)獨立研究和創(chuàng)新能力。課程內容：基本概念：算法的定義、性質、 分析算法的基本方法等分治策略（Divide and conquer）貪心方法（Greedy method）動態(tài)規(guī)劃（Dynamic Programming）圖算法

6、（Graph Algorithms）回溯與分枝限界專題綜合實踐本課程需要的基礎u 數據結構u 程序設計語言（C/C+）：結構化設計u 數學基礎u 操作系統(tǒng)、編譯 授課形式:l課堂教學：（）l課堂討論：專題、解題報告l上機實踐：需要提交實驗報告考核方式:l考試：（）l綜合成績=卷面成績*80% + 平時成績*20%l平時成績=作業(yè)+上機實驗+考勤主要參考書l計算機算法基礎， 余祥宣等編著， 華中科技大學出版社lIntroduction to algorithms, Thomas H. Cormen,etc., third edition, The MIT Press.lAlgorithm Des

7、ign，Michael T. Goodrichl算法設計與分析，王曉東，清華大學出版社其它參考書lThe Art of Computer Programming, Donald E.Knuth. Volume 1-3, Second Edition.l Data Structures, Algorithms, and Applications in C+(Part 3) Sartaj Sahni, China Machine Pressletc.一、算法基礎參考資料：l計算機算法基礎 第二章 l Introduction to algorithms Chapter 1、 Chapter 31.

8、1 算法的定義及特性1. 什么是算法？如數字、計算一樣，算法是一個基本概念。算法是解一確定類問題的任意一種特殊的方法。在計算機科學中，算法是使用計算機解一類問題的精確、有效方法的代名詞； 算法是一組有窮的規(guī)則，它規(guī)定了解決某一特定類型問題的一系列運算。對算法概念的理解算法由運算組成 算術運算、邏輯運算、賦值運算、過程調用算法有其特殊性 解決不同問題的算法是不相同的，有沒有一個萬能的算法？算法是有窮的計算過程 靜態(tài)上：規(guī)則/運算/語句的數量有窮 動態(tài)上：計算過程/計算時間有限我們已經接觸過的算法： 分類（排序）算法：將已知的n個元素按照關鍵值大小的非增/非降順序重新排列。如：冒泡排序、插入排序、

9、歸并排序 查找算法：從已知的元素集合中找出滿足要求的一個或一組元素。如：順序查找、二分查找、第k小元素 圖算法： 在已知的圖中找出滿足某些性質的結點或邊。 如：最短路徑算法、最小成本生成樹思考：p我們學會了解決一個個具體問題的算法，那么在這些算法的設計中有沒有一些共性的東西？有沒有可以總結出來的規(guī)律、規(guī)則和方法？這些規(guī)律、規(guī)則和方法對于其它算法的設計有沒有指導意義？p能不能找到一些算法設計的一般策略、技術和方法？算法：求解問題的一組規(guī)則檢索問題 分治策略排序問題 貪心策略 路徑問題 規(guī)則的設計 設計策略 動態(tài)規(guī)劃 最優(yōu)化問題 檢索遍歷問題 回溯 分枝限界 .發(fā)現(xiàn)指導形成算法產生算法設計的指導思

10、想和基本規(guī)律 較高的算法設計能力不僅在于簡單地使用一些具體的算法，更在于對算法設計方法的掌握上。只有深入理解算法設計的策略、技術和方法，才能在面對新問題時創(chuàng)造出新的算法。 算法學習要做到：u深入理解算法設計的一般規(guī)律、技術和方法u靈活運用現(xiàn)有的算法解決實際問題u在改造客觀世界的過程中，運用學到的知識創(chuàng)造新的算法，解決新的問題2. 算法的五個重要特性 確定性、能行性、輸入、輸出、有窮性1）確定性：算法使用的每種運算必須要有確切的定義，不能有二義性。 例：不符合確定性的運算l 5/0 l 將6或7與x相加l 未賦值變量參與運算2）能行性 算法中有待實現(xiàn)的運算都是基本的運算，原理上每種運算都能由人用

11、紙和筆在“有限”的時間內完成。 例：整數的算術運算是“能行”的 實數的算術運算可能是“不能行”的如何認識算法的確定性和能行性？u確定性和能行性是算法設計過程可能存在的問題。u一個實際的程序設計語言定義了該語言中可以使用的數據類型和能夠參與的運算，編譯器可以對程序中的非法運算檢錯。非確定、非能行的“臆造”運算是不能存在的，程序的正確性主要在于邏輯正確。u但算法本身的正確性不僅在于此。3）輸入 每個算法都有0個或多個輸入。這些輸入是在算法開始之前給出的量，取自于特定的對象集合定義域4）輸出 一個算法產生一個或多個輸出，這些輸出是同輸入有某種特定關系的量。算法的狀態(tài)轉換 算法：把特定的輸入轉換成需要

12、的輸出。算法輸入輸出u狀態(tài)：算法/程序中一組變量的當前值稱為算 法/程序的當前狀態(tài)。u算法：狀態(tài)轉換器，算法把輸入時的初始狀態(tài) 轉換為輸出時的終止狀態(tài)5）有窮性 一個算法總是在執(zhí)行了有窮步的運算之后終止。p計算過程：滿足確定性、能行性、輸入、輸出， 但不一定滿足有窮性的一組規(guī)則。 算法和計算過程的關系： 計算過程：操作系統(tǒng)(不終止的運行過程) 算法是“可以終止的計算過程”p時效性：實際問題往往都有時間要求。例：國際象棋（啟發(fā)） 數值天氣預報 只有在要求的時間內解決問題才是有意義的。 針對算法的時效性，只有把在相當有窮步內終止的算法投入到計算機上運行才是實際可行的。 何為“相當有窮”？ 通過算法

13、分析，了解算法速度，給出算法計算時間的一個精確的描述，以衡量算法的執(zhí)行速度，選擇合適的算法解決問題。 注：算法分析還包括空間分析。與算法學習相關的內容五個方面：設計、表示、證明、分析、測試1）設計：構思算法的處理規(guī)則，創(chuàng)造性的活動。2）表示：用語言把算法描述出來。類計算機語言、偽代碼 （SPARKS語言、類C語言）、流程圖、自然語言等3）證明：證明算法的正確性。 正 確 性：對合法輸入能得出正確的答案。 算法證明：證明算法的正確性，與語言無關 程序證明：證明程序的正確性(理論證明，程序邏輯) 一個例子：插入分類輸入：n個元素存放在數組A中：A1An，無序輸出：按照從小到大的順序重新整理的有序數

14、組A插入分類算法的設計思想： 1. 將第一個元素（A1）看作只有一個元素的有序子序列； 2. 置循環(huán) i=2 to n，將Ai插入到由A1Ai-1元素組成的有序子序列中。思考問題： l上述設計思路對嗎？l如何實現(xiàn)？ SPARKS語言算法描述： procedure INSERTIONSORT(A,n) A(0)- /A0做監(jiān)視哨 for i2 to n do /從第二個元素開始循環(huán) itemA(i); /將Ai放到臨時變量item中 ji-1 /從后往前查找當前元素的插入位置 while itemA(j) do A(j+1)A(j); /比item大的元素往后移一位 jj-1; /繼續(xù)往前查找

15、repeat A(j+1) item; /將item插入到正確的位置上 repeat end INSERTIONSORT 算法導論算法描述： INSERTIONSORT(A,n) A0- A0做監(jiān)視哨 for i2 to n 從第二個元素開始循環(huán) do itemAi 將Ai放到臨時變量item中 ji-1 從后往前查找當前元素的插入位置 while itemAj do Aj+1Aj 比item大的元素往后移一位 jj-1; 繼續(xù)往前查找 A(j+1) item; 將item插入到正確的位置上 基于上述算法，思考：u這個算法描述正確嗎？ 能行、確定、輸入、輸出、有窮？ 正確性證明u運算得快嗎？

16、時間復雜度分析u使用了多少內存？ 空間復雜度分析進一步我們需要回答：u它能夠應用到那些領域？ 要做深入進一步分析 u利用不同語言實現(xiàn)需要那些技巧? 實現(xiàn)4）分析：對算法的時、空特性做定性、定量分析，以了解算法的性質。5）測試：將算法變成程序，放到計算機上運行，觀察運行情況 編程中的調試：排錯過程?！罢{試只能指出有錯誤， 而不能指出它們不存在錯誤” Dijkstra的名言 運行中的測試：分析過程。作時空分布圖，驗證分析結論，進一步優(yōu)化算法的設計。 本課程集中于學習算法的設計與分析。通過學習，掌握計算機算法設計和分析基本策略與方法，為設計更復雜、更有效的算法奠定基礎1. 分析算法的目的 算法選擇的

17、需要：對同一個問題可以設計不同的算法，不同算法的時間和空間特性是不同的 算法優(yōu)化的需要：有沒有可以改進的地方，以使算法工作得更好？ 分析算法的目的在于：通過對算法的分析了解算法的性能，1）可以在解決同一問題的不同算法之間比較性能的好壞，從而運行好的算法，改進差的算法，避免無益的人力和物力浪費。2）可以對算法的性質作深入了解，從而可以進一步優(yōu)化算法，讓其更好地工作。1.2 分析算法基礎2. 重要的假設和約定1）計算機模型的假設計算機形式理論模型： 有限狀態(tài)自動機、Turing機通用的順序計算機模型：u單CPU串行算法u有足夠的“內存”，并能在固定的時間內存取 數據單元 RAMrandom-acc

18、ess machine 區(qū)分計算機的理論模型與實際的計算機 2）計算的約定 算法的執(zhí)行時間是算法中所有運算執(zhí)行時間的總和，可以表示為: 算法的執(zhí)行時間= 其中， fi ：是運算i的執(zhí)行次數，稱為該運算的頻率計數 僅與算法的控制流程有關，與實際使用的計算機硬 件和編制程序的語言無關。 ti ：是運算i在實際的計算機上每執(zhí)行一次所用的時間 與程序設計語言和計算機硬件有關。 如何確定算法使用了哪些運算,每種運算的fi和ti又是多少?iitf運算的分類 依照運算的時間特性，將運算分為時間囿界于常數的運算和時間非囿界于常數的運算。 囿界的含義：限于. 時間囿界于常數的運算： 基本算術運算，如整數、浮點數

19、的加、減、乘、除 字符運算、賦值運算、過程調用等 特點：執(zhí)行時間是固定量，與具體的操作數無關。 例： 1+1 = 2 vs 10000+10000 = 20000 100*100 = 10000 vs 10000*10000 = 100000000 CALL INSERTIONSORT更一般的情況 設有n種運算c1，c2，cn，它們的執(zhí)行時間分別是t1，t2，tn。 令t0=max(t1，t2，tn)，則每種運算執(zhí)行一次的時間都可以用t0進行限界(上界)。 視t0為一個單位時間，則這些運算“理論”上都可視為僅花一個固定的單位時間t0即可完成的運算 稱具有這種性質的運算為時間囿界于常數的運算。運

20、算的分類（續(xù)） 時間非囿界于常數的運算：u字符串操作：與字符串中字符的數量成正比 例：字符串的比較運算（strcmp）u記錄操作：與記錄的屬性數、屬性類型等有關 特點：運算時間與操作數相關，每次執(zhí)行的時間是一個不定的量。 怎么分析時間非囿界于常數的運算？ 這類運算通常是由更基本的運算組成的。而這些基本運算是時間囿界于常數的運算。 如：字符串的比較運算是由一組字符比較運算組成的。 非囿界于常數的運算的一次執(zhí)行時間是其包含的所有基本運算的執(zhí)行時間之和： 如：字符串比較時間tstring = Length（String）* tchar 故：分析時間非囿界于常數的運算時，只需將其分解成若干時間囿界于常

21、數的運算即可。3）工作數據集的選擇算法的執(zhí)行情況與輸入數據的特征有關，體現(xiàn)在： 算法的執(zhí)行時間與輸入數據的規(guī)模相關，一般 規(guī)模越大，執(zhí)行時間越長。 在不同的數據配置上，同一算法有不同的執(zhí)行 情況，可分為最好、最壞和平均等情況討論。編制不同的數據配置，分析算法的最好、最壞、平均工作情況是算法分析的一項重要工作。 如插入排序有最好O(n)、最壞O(n2)的工作情況。注：編制測試數據對算法分析與程序調試都是關鍵的，但目的不同。u算法分析數據集：反映算法的典型執(zhí)行情況（最好、最壞、平均）；u調試程序數據集：排錯。力求走到程序的每個分支，驗證各種情況下程序執(zhí)行正確與否。3.如何進行算法分析？ 對算法的全

22、面分析將分兩個階段進行：事前分析和事后測試（理論分析和程序測試）。事前分析：求算法時間/空間復雜度的限界函數。p限界函數通常是關于問題規(guī)模n的特征函數，被表示成、或的形式。如歸并排序的O(nlogn)。p特征函數是通過分析算法的控制邏輯得來的，是對算法所用運算執(zhí)行次數的統(tǒng)計結果。與使用的程序設計語言和計算機硬件無關。事后測試：將算法編制成程序，放到實際的計算機上運行，收集程序的執(zhí)行時間和空間占用情況等統(tǒng)計數據，然后進行分析判斷。p事后測試與物理實現(xiàn)直接有關。 算法分析主要集中于與物理實現(xiàn)無關的事前分析階段獲取算法的理論時間/空間復雜度。1）事前分析目標：獲取算法的時間（空間）復雜度函數，從理論

23、上分析算法性能的好壞。可以分為時間、空間兩個方面： 時間分析：p了解算法中使用了哪些運算(主要是具有單位執(zhí)行時間的基本運算)。p分析程序的控制流程，從而確定各類運算的執(zhí)行次數。p將對運算執(zhí)行次數的統(tǒng)計分析結果表示成關于問題規(guī)模n的特征函數。p算法性能有最好、平均、最壞等情況，與數據配置有關。分析典型的數據配置，了解算法在各種情況下的執(zhí)行情況?？臻g分析：p分析算法中各類變量的定義情況和使用情況p將空間占用量表示成為問題規(guī)模n的特征函數。p空間占用有最大、平均、最少等情況，與數據配置有關。分析典型的數據配置，了解算法在各種情況下的空間占用情況。如何進行時間分析？（一）統(tǒng)計算法中各類運算的執(zhí)行次數

24、頻率計數 統(tǒng)計對象：運算 1）基本運算：指那些時間囿界于常數的運算 2）復合運算：具有固定執(zhí)行時間的程序塊，如一條語句、一個過程或函數等，它們的一次執(zhí)行時間也可視為常量、單位時間。 頻率計數：運算的執(zhí)行次數是從算法的控制流程得來的。 順序結構中的運算：執(zhí)行次數計為1 嵌套結構中的運算：執(zhí)行次數等于被循環(huán)執(zhí)行的次數 控制流程分析的關鍵：確定算法中使用的嵌套結構，包括循環(huán)語句、嵌套調用等。 例：執(zhí)行次數的統(tǒng)計 xx+y for i 1 to n do for i 1 to n do x x + y for j 1 to n do repeat x x +y repeat repeat (a) (b

25、) (c) 分析： (a)： xx+y執(zhí)行了1次 (b)： xx+y執(zhí)行了n次 (c)： xx+y執(zhí)行了n2次 for i 1 to n do for j i to n do x x +y repeatrepeat(d)（二）將頻率計數表示成問題規(guī)模n的函數： 如： an2+ bn+c 算法的執(zhí)行時間是算法中各類運算執(zhí)行時間之和，將正比于各類運算的頻率計數之和。 事前分析的頻率計數結果與所使用的機器及其他環(huán)境因素無關（如程序設計語言、編譯器），只與算法本身的控制流程有關。例：插入分類 procedure INSERTIONSORT(A,n) /將A(1：n)中的元素按非降次序分類，n1/ 執(zhí)行

26、次數 單位執(zhí)行時間 A(0)-/設置初始邊界值 1 t1 for j2 to 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 令 t0=max(t1,t2,t3,t4,t5,t6,t7)，則74262524321) 1() ) 1()1()() 1() 1()

27、1()(tntitititntntntnTninini)( )( )1() ) 1()1()() 1() 1() 1(1 ()(2020222nOtcbnantniiinnnnTninini最壞情況（逆序）最好情況（正序）(n) ) 1() 1() 1() 1() 1()(754321bantntntntntntnT進一步的分析： 主要針對算法最主要的部分進行分析，抓住主要矛盾即可，如插入排序中,可以僅集中于對for/while雙重嵌套循環(huán)的分析，而忽略順序或執(zhí)行次數較低的部分。（三）函數表達式的數量級（階） 函數表達式中的最高次項的次數，稱為函數表達式的數量級，是衡量頻率計數的“大小”的一種

28、測度。 數量級從本質上反映了算法復雜度的高低數量級越小，算法的復雜度越低，同等規(guī)模下算法執(zhí)行時間越短。反之，數量級越大，算法的復雜度越高，同等規(guī)模下算法執(zhí)行時間越長。 例：假如求解同一個問題的三個算法分別具有n， n2 ， n3 數量級。 若n=10，則可能的執(zhí)行時間將分別是10，100，1000 個單位時間與環(huán)境因素無關。實例：工資的級別 （定性的表示）（四）限界函數 一般用頻率計數函數表達式中的最高次項表示算法復雜性分析的最終結果 限界函數，且忽略掉其系數，記為： g(n)。g(n)通常是關于n的形式簡單的函數式，如：logn，nlogn，n2等。 不同算法的g(n)有不同的具體形式。 g

29、(n)通常是對算法中最復雜的計算部分分析而來的。 g(n)忽略了函數表達式中次數較低的“次要”項，體現(xiàn)了算法復雜性的最本質特征。 g(n)通常取單項的形式?？臻g特性分析（與時間特性的分析類似，略） 2）事后測試n把算法編制成程序，在實際的計算機硬件平臺上運行程序，統(tǒng)計執(zhí)行中實際耗費的時間與空間，與事前分析的結論進行比較，驗證先前的分析結論是否正確，并優(yōu)化所設計的算法。n分析手段：作時、空性能分布圖4. 計算時間的漸近表示、的定義 算法時間/空間復雜度的限界函數常用的有三個：上界函數、下界函數、“均值”函數。定義如下： 記：算法的實際計算時間為f(n)，計算時間的限界函數為g(n)，其中，un是

30、問題規(guī)模的某種測度。uf(n)是與機器及語言有關的量。ug(n)是事前分析的結果，是一個形式簡單的函數，與頻率計數有關、而與機器及語言無關。 1）O、記號定義1. 1（上界函數）如果存在兩個正常數c和n0，對于所有 的nn0，有|f(n)| c|g(n)|，則記作f(n) = (g(n)。 含義：u如果算法用n值不變的同一類數據（規(guī)模相等，性質相同）在某臺機器上運行，所用的時間總小于|g(n)|的一個常數倍。u函數f 至多是函數g 的c倍，除非nn0。即是說，當n 充分大時，g 是f 的一個上界函數（在一個非零常數倍的意義下）。u這時候也稱f(n)的數量級就是g(n)。)()(:,)()(00

31、ncgnfnnncngOnf g(n)是通過對算法中運算的使用情況分析而得出的函數表達式，通常情況下，取函數式里的最高次項，舍掉低階項和常數（因為低階項和常數最終被湮滅在高次項里），且忽略系數。如：c=O(1)：f(n)等于非零常數，可看作n04n+3=O(n) ：可取c5，n03100n+6=O(n) ：可取 c=101，n0662n+n2=O(2n) ：可取c =7，n0=4 10n2+4n+3=O(n2)3log n + 2n + n2 =O(n2)nlog n +n2=O(n2)注：1總是試圖求出數量級最小的g(n)作為f(n)的上界函數，即， g(n)應該盡量接近函數f(n)。數量級

32、越小，限界越精確。 如 若：3n+2=O(n2) 則是松散的界限； 而：3n+2=O(n) 就是較緊的界限。2不要產生錯誤界限。 如，n2+100n+6，當n3 時，n2+100n+6c-100 就有 n2+100n+6cn。 提示：注意大系數低次項的影響 同理，3n2+42n=O(n)也是錯誤的。3 f(n)=O(g(n)不能寫成g(n)=O(f(n)。 f(n)與g(n)并不等價，這里的等號也并不是通常相等的含義。 O更精確的定義可以用集合表示： O(g(n)=f(n)|f(n)滿足：存在正的常數c 和n0，使得當n n0 時，f(n) cg(n) 這里O(g(n)是一個集合，f(n)=O

33、(g(n)讀作： “f(n)是g(n)的一個大O 成員” 記作：f(n) O(g(n) 但通常寫作：f(n)=O(g(n)。（以上內容參見Intruduction to AlgorithmChapter 3， 、 相同） 定理1.1 大O比率定理 對于函數f (n)和g (n)，若 存在，則 f (n)=O (g (n) )，當且僅當存在確定的常數c，有 c。證明： 1）如果f (n)=O (g (n) )，則存在c 0及某個n0，使得對于所有的nn0，有f (n) /g(n)c，因此 c。 2）假定 c，它表明存在一個n0，使得對于所有的nn0，有f (n)max1, c *g (n)。證畢

34、。)()(limngnfn)()(limngnfn)()(limngnfn)()(limngnfn例：因為 ，所以5n+2 = O(n) 因為 ，所以7n2+5n+2 = O(n2) 因為 ，所以52n+n2 = O(2n)考察下式： 因為 ，所以n9+3n2 = O(2n)，是否合適？顯然這不是一個好的上界估計。 原因在于：極限值不是一個正常數（見O的定義）。525limnnn7257lim22nnnn5225lim2nnnn023lim29nnnn用于估算復雜性階的定理定理1.2 對于任意正實數x 和 ，有下面的不等式：1) 存在某個n0 , 使得對于任何nn0 , 有(log n)x(l

35、og n)x+ 2) 存在某個n0 , 使得對于任何n n0 ，有(log n)x n。3) 存在某個n0 , 使得對于任何n n0，有nxnx+ 。4) 存在某個n0 , 使得對于任何nn0 ，有nx2n。5) 對任意實數y , 存在某個n0，使得對于任何nn0， 有 nx (log n)y nx+ 例: 根據定理1.2，很容易得出： n3 + n2 log n = O(n3 ) ； n4 + n2.5 log20 n = O(n4 )； 2n n4 log3 n2n n5 / log3 n = O(2n n5 )。定義1.2（下界函數） 如果存在兩個正常數c和n0，對于所有的nn0，有|f

36、(n)| c|g(n)|，則記作f(n) = (g(n)。含義：u如果算法用n值不變的同一類數據在某臺機器上運行，所用的時間總不小于|g(n)|的一個常數倍。u函數f 至少是函數g 的c 倍，除非n n0 。即是說，當n 充分大時，g 是f 的一個下界函數（在一個非零常數倍的意義下）。注：1. 通常情況下，下界函數也取單項的形式。2. 總是試圖求出數量級最大的g(n)作為f(n)的下界函數，g(n)應該盡量接近函數f(n)。3. 類似于大O 符號，可以參考定理1.2 所列的不等式，來估計復雜性函數的下界。其它具有和大O類似的性質。 定理1.3 大比率定理 對于函數f (n)和g (n)，若 存

37、在，則 f (n)= (g (n) )，當且僅當存在確定的常數c，有 c。注： 這里，當n充分大時，g(n) cf (n)意味著 ， 由此不難看出上述判別規(guī)則的正確性。)()(limnfngn)()(limnfngn)(1)(ngcnf定義1.3（“平均情況”） 如果存在正常數c1，c2和n0，對于所有的nn0，有 c1|g(n)| |f(n)| c2|g(n)|， 則記作含義：u算法在最好和最壞情況下的計算時間就一個常數因子范圍內而言是相同的。可看作： 既有 f(n) = (g(n)，又有f(n) = (g(n)u函數f 介于函數g 的c1和c2倍之間，即當n充分大時， g 既是f 的下界，

38、又是f 的上界。)()(ngnf 定理1.4 大比率定理 對于函數f (n)和g (n)，若 和 都存在，則 f (n)= (g (n) )，當且僅當存在確定的常數c1和c2，有 c1和 c2。)()(limnfngn)()(limnfngn)()(limngnfn)()(limngnfn2）關于算法復雜度的討論(1) 數量級的大小對算法的有效性有決定性的影響。 以上界函數O(g(n)為例， 例：假設解決同一個問題的兩個算法，它們都有n個輸入, 計算時間的數量級分別是n2和nlogn。則， n=1024：分別需要1048576和10240次運算。 n=2048：分別需要4194304和2252

39、8次運算。 可以看到： 同等規(guī)模n=1024下，計算量有近百倍的差距； 而在規(guī)模加倍后，一個(n2)的算法計算時間增長4倍，而一個(nlogn)算法則只增長一倍多一點。（2）算法時間復雜度的分類 根據上界函數的特性，可以將算法分為：多項式時間算法和指數時間算法。多項式時間算法：可用多項式函數對計算時間限界的 算法。常見的多項式限界函數有： (1) (logn) (n) (nlogn) (n2) (n3)指數時間算法：計算時間用指數函數限界的算法。常見的 指數時間限界函數： (2n) (n！) 0，ad(n)是O(f(n)； 常數不影響數量級(2)如果d(n)是O(f(n), e(n)是O(g(

40、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)對于任意固定的x0和a1，nx是O(an)；(5)對于任意固定的x0，lognx是O(logn)；這里x是常數(6)對于任意固定的常數x0和y0，logxn是O(ny)；例：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、多項式定理 2n3+4n2

41、logn=O(n3) 4）o,記號定義1.4 o記號形式1：對任意正常數c，存在常數n00，使對所有的nn0，有|f(n)| c|g(n)|，則記作： f(n) = o(g(n)。形式2：若 則記f(n) = o(g(n)。例：2n = o(n2)，但2n2 o(n2)0)()(limngnfnO和o的區(qū)別O：o：在o表示中，當n趨于無窮時，f(n)相對于g(n)來說已經不重要了。)()( :,)()(00ncgnfnnncngOnf)()( :,)()(00ncgnfnnncngonf定義1.5 記號形式1：對任意正常數c，存在常數n00，使對所有的nn0，有c|g(n)|f(n)| ，則記作： f(n) = (g(n)。形式2：若 則記f(n) = o(g(n)。例：n2/2 = (n)，但n2/2 (n2)()(limngnfn和的區(qū)別