算法設(shè)計與分析-第1章算法分析基本概念

1、算法設(shè)計與分析 算法分析基本概念算法分析基本概念主要內(nèi)容： 介紹算法分析的基本概念和基本方法。 算法分析基本概念一. 算法 (1.1) D.E.Knuth的非形式化定義 一個算法，就是一個有窮規(guī)則（指令）集合。它為某個特定類型問題提供了解決問題的運算序列。 算法的五個特性1. 有窮性 4. 輸出2. 確定性 5. 輸入3. 可行性算法分析基本概念二. 可計算性和計算復(fù)雜性 (1.2) 1.可計算性 “幾乎所有”的問題都計算機不可解。可解問題集合為可數(shù)的（對應(yīng)整數(shù)集）所有問題集合為不可數(shù)的（對應(yīng)實數(shù)集） 所以，不可解問題集合為不可數(shù)的。算法分析基本概念二. 可計算性和計算復(fù)雜性 (1.2) 1.

2、可計算性 不可解問題之例：確定的十進制表示形式中是否存在7個連續(xù)的1。停機問題：給定一個帶輸入的計算機程序，它會停機嗎？（由英國數(shù)學(xué)家Turing 證明該問題計算機不可解） 可計算性理論研究問題的可解性。 算法分析基本概念二. 可計算性和計算復(fù)雜性 (1.2) 2.計算復(fù)雜性 可解的問題并不一定是實際可接受的。 例：求26個小寫字母的所有排列。 共有26！種不同排列，設(shè)計算機每秒可完成109種排列的計算，共需要花多少時間才能完成所有計算？ 26!4x1026 一年共有365x24x3600秒=3.1586x107秒 大約要花1.2x1010年。 算法分析基本概念二. 可計算性和計算復(fù)雜性 (1

3、.2) 2.計算復(fù)雜性 對于實際可接受的同一問題，不同算法可能在效率上有很大差異。 例1.4 兩種排序算法的比較 (P12) n SELECTSORT BOTTOMUPSORT (排序數(shù)據(jù)個數(shù)) (選擇排序) (歸并排序) n=128時的比較時間 0.008秒 0.0008秒 n=220時的比較時間 6.4天 20秒 算法分析基本概念二. 可計算性和計算復(fù)雜性 (1.2) 2.計算復(fù)雜性 計算復(fù)雜性研究計算機可解問題的效率（解決 問題所需的時間和空間） 計算復(fù)雜性包括時間復(fù)雜性和空間復(fù)雜性。 算法分析基本概念三. 時間復(fù)雜性 (1.8) 1.有關(guān)定義 算法的運行時間分析應(yīng)滿足： 獨立于計算機系

4、統(tǒng)，獨立于描述語言。（僅取決于算法本身） 算法的時間復(fù)雜性指算法中元運算的執(zhí)行次 數(shù)，其為問題規(guī)模的函數(shù)。 算法分析基本概念三. 時間復(fù)雜性 (1.8) 1.有關(guān)定義 元運算（定義1.1, P14） 常見的元運算：基本算術(shù)運算、邏輯運算、賦值運算等。 問題規(guī)模通常指輸入大?。ㄝ斎霐?shù)據(jù)量的大小）。 算法分析基本概念三. 時間復(fù)雜性 (1.8) 1.有關(guān)定義 從實際出發(fā)，算法的時間復(fù)雜性分析不必精確計算（近似的），而且只關(guān)心問題規(guī)模充分大時的情況（增長率）。（為何？） 例1.4 表1.1 (P14) 表1.1.doc(2) 算法的漸進時間復(fù)雜性指當(dāng)問題規(guī)模充分大時 對時間復(fù)雜性的估計，用O, ,

5、估計。算法分析基本概念三. 時間復(fù)雜性 (1.8) 1.有關(guān)定義 (3) O, , 的定義（P15-16 定義1.2-1.4） f(n)= (g(n) 當(dāng)且僅當(dāng) g(n)=O(f(n) f(n)= (g(n)當(dāng)且僅當(dāng) f(n)= O(g(n) 且 f(n)= (g(n) 例：n2=O(n3) n3=(n2) 3n2=O(n2)=(n2)=(n2)算法分析基本概念三. 時間復(fù)雜性 (1.8) 1.有關(guān)定義 增長率（在忽略常數(shù)因子的前提下） f(n)=O(g(n): f(n)的增長率不高于g(n), f(n)的階=g(n)的階。 f(n)=(g(n): f(n)的增長率等于g(n), f(n)的階

6、=g(n)的階。 見圖1.5 (P13) 算法分析基本概念三. 時間復(fù)雜性 (1.8) 1.有關(guān)定義 在忽略常數(shù)因子的情況下，O, , 分別提供 了算法運行時間的一個上界、下界、確切界限。 算法分析基本概念三. 時間復(fù)雜性 (1.8) 2. 時間復(fù)雜性的階 根據(jù)可將算法分類，同階的算法屬同一復(fù)雜 性類（等價類） (1) 常見的算法復(fù)雜性的階 (1) (n) (np) (log n) (np logq n) (an) (n!) (nn) 其中，p, q0 , a1。 算法分析基本概念三. 時間復(fù)雜性 (1.8) 2. 時間復(fù)雜性的階 (2) 階的大小的比較 o符號：（定義1.5 P19） 例：

7、=o(n) log n=o(n) f(n)=o(g(n) f(n)=O(g(n) 且 g(n)O(f(n) f(n)=O(g(n) 且 f(n)(g(n) f(n)=o(g(n): f(n)的增長率低于g(n), f(n)的階g(n)的階, 用f(n) g(n)表示。算法分析基本概念三. 時間復(fù)雜性 (1.8) 2. 時間復(fù)雜性的階 (2) 階的大小的比較 常用階的比較：常用階的比較.doc 階的比較方法：根據(jù)O, , 的定義，利用 已知結(jié)論，利用極限運算等。 階的比較之例： (np)稱多項式階，(logq n)稱對數(shù)階， (an)稱指數(shù)階。算法分析基本概念三. 時間復(fù)雜性 (1.8) 2.

8、時間復(fù)雜性的階 (3) 函數(shù)階的估計： 取最高階的項估計，且可忽略常數(shù)因子 。 例：f(n)=amnm + am-1nm-1+ a1n + a0 利用不等式估計： 例1.12, 1.13 (P17-18)算法分析基本概念四. 空間復(fù)雜性 （1.9） 算法的空間復(fù)雜性指算法執(zhí)行過程中所 需的內(nèi)存空間(即輔助空間)，不包括存儲輸入所用的空間。 空間復(fù)雜性的分析類似于時間復(fù)雜性。 時間和空間資源的權(quán)衡時間復(fù)雜性和空間復(fù)雜性的關(guān)系算法分析基本概念五. 算法時間復(fù)雜性的估計 （1.11）1. 計算迭代（循環(huán)）次數(shù) 算法的時間復(fù)雜性往往取決于算法所執(zhí)行的循環(huán)次數(shù)，該情況下只要計算算法中最大的循環(huán)次數(shù)。 示

9、例 時常循環(huán)次數(shù)難以計算。算法分析基本概念五. 算法時間復(fù)雜性的估計 （1.11）2. 計算基本運算的頻度 基本運算：（定義1.6 P24） 基本運算之例：基于比較的查找和排序算法中的比較運算圖（樹）的遍歷算法中的訪問頂點（節(jié)點）的操作 計算算法中基本運算的頻度，可得算法的時間 復(fù)雜性。算法分析基本概念五. 算法時間復(fù)雜性的估計 （1.11）2. 計算基本運算的頻度 例：合并兩個有序表: 算法1.3 （P6） 基本運算為賦值運算， 頻度為m+n= (m+n), m,n為兩個有序表的長度。 二分插入排序: 算法1.12 (p25) 基本運算不是比較而是移動（賦值）。算法分析基本概念五. 算法時間

10、復(fù)雜性的估計 （1.11）3. 利用遞推（遞歸）關(guān)系 遞歸算法的時間復(fù)雜性常常滿足遞歸 關(guān)系，通過解遞歸方程可求的算法的時 間復(fù)雜性。 該方程的解為C(n)=1+算法分析基本概念五. 算法時間復(fù)雜性的估計 （1.11）3. 利用遞推（遞歸）關(guān)系 例：二分查找: 算法1.2 (p4) 該算法的最大比較次數(shù)C(n)滿足如下遞歸方程： 該算法的時間復(fù)雜性為O(log n)。算法分析基本概念六. 最壞情況和平均情況時間復(fù)雜性的估計 （1.12） 常常算法對同樣大小的不同輸入實例 運行時間不同。 例：二分查找: 算法1.2 (P4) 插入排序：算法1.5 (P8) 圖1.6 （P27）算法分析基本概念六

11、. 最壞情況和平均情況時間復(fù)雜性的估計 （1.12）1. 最壞情況下時間復(fù)雜性 W(n)= 其中，Dn是大小為n的輸入集合， t(I)是輸入為I時算法的運算時間。 算法分析基本概念六. 最壞情況和平均情況時間復(fù)雜性的估計 （1.12）1. 最壞情況下時間復(fù)雜性 例：插入排序算法 W(n)= =n(n-1)/2=(n2) 例：二分查找算法的最壞情況下時間復(fù)雜性為 (log n)。算法分析基本概念六. 最壞情況和平均情況時間復(fù)雜性的估計 （1.12）2. 平均情況下時間復(fù)雜性 其中，Dn是大小為n的輸入集合， t(I)是輸入為I是時算法的運算時間, p(I)是輸入I出現(xiàn)的概率。 例1.30: 順序查找算法 ( P28 )算法分析基本概念七. P與NP 1. P: 存在多項式階的時間復(fù)雜性算法的問題 集合。 P中的問題為實際可接受的，且一般存在低次多項式階的算法。2. 困難的問題：目前還不能證實是屬于P的 問題。 困難的問題為實際不可接受的，其算法一般為指數(shù)階或更高階。3. NP: 一類困難問題的集合。算法分析基本概念七. P