計算復(fù)雜性和算法分析計算機(jī)科學(xué)導(dǎo)論第六講（陳意云）.ppt

1、計算復(fù)雜性和算法分析計算機(jī)科學(xué)導(dǎo)論第六講,計算機(jī)科學(xué)技術(shù)學(xué)院 陳意云,課 程 內(nèi) 容,課程內(nèi)容 圍繞學(xué)科理論體系中的模型理論, 程序理論和計算理論 1. 模型理論關(guān)心的問題 給定模型M，哪些問題可以由模型M解決；如何比較模型的表達(dá)能力 2. 程序理論關(guān)心的問題 給定模型M，如何用模型M解決問題 包括程序設(shè)計范型、程序設(shè)計語言、程序設(shè)計、形式語義、類型論、程序驗證、程序分析等 3. 計算理論關(guān)心的問題 給定模型M和一類問題, 解決該類問題需多少資源,本講座用簡單的例子來扼要介紹計算復(fù)雜性和算法分析,2,講 座 提 綱,基本知識 可計算理論, 計算資源, 計算復(fù)雜性理論, 算法分析 復(fù)雜性的計量

2、問題規(guī)模、復(fù)雜性函數(shù)、最壞、最好和平均三種情況的時間復(fù)雜性 復(fù)雜性的漸近行為及其階 復(fù)雜性的漸近行為、漸近意義下的記號O、記號O的運算規(guī)則、復(fù)雜性漸近階分析的重要性 算法復(fù)雜性漸近階的分析 算法的復(fù)雜性漸近階的分析、語句規(guī)則的例舉,3,基 本 知 識,可計算理論 研究計算的一般性質(zhì)的數(shù)學(xué)理論，也稱算法理論 通過建立計算的數(shù)學(xué)模型, 區(qū)分可計算與不可計算 可計算函數(shù)：能夠在抽象計算機(jī)上編出程序計算其值的函數(shù)。這樣的程序稱為算法 這樣就可以討論哪些函數(shù)是可計算的，哪些函數(shù)是不可計算的 可計算性：指一個實際問題是否可以使用計算機(jī)來解決（能解決一定是指有限步內(nèi)解決） 上一講介紹的就是計算模型和可計算函

3、數(shù),4,基 本 知 識,計算資源 在計算復(fù)雜性理論內(nèi)，計算資源是指在某個計算模型之下，求解一個問題所要消耗的資源 時間資源：求解問題所需花費的時間，通常用計算步數(shù)來度量 空間資源：求解問題所需占用的空間，通常用存儲器空間的大小來度量 計算所需資源的多少是衡量計算復(fù)雜性的依據(jù) 實際應(yīng)用關(guān)心的資源與理論上的有區(qū)別：硬件資源（如計算機(jī)、存儲器）、軟件資源、網(wǎng)絡(luò)資源（如通信帶寬）等,5,基 本 知 識,計算復(fù)雜性理論 是理論計算機(jī)科學(xué)和數(shù)學(xué)的一個分支，它致力于將可計算問題根據(jù)其本身固有的難度進(jìn)行分類，以及把這些類別相互聯(lián)系起來 它嘗試把問題分成兩類：在適當(dāng)?shù)馁Y源限制下能解(容易)和不能解(困難)的問題

4、。一個問題，若求解需很多資源(無論什么算法), 則被認(rèn)為是難解的 通過引入計算模型來研究這些問題，并給出定量計算解決問題所需的資源 (時間和空間) 的方法，由此把確定資源的方法數(shù)學(xué)化 作用之一是確定計算機(jī)能解和不能解的實際界線,6,基 本 知 識,計算復(fù)雜性理論 研究問題之一：NP =? P P (Polynomial)：在確定型圖靈機(jī)上有多項式時間算法的問題的集合 NP (Nondeterministic Polynomial)：在非確定型圖靈機(jī)上有多項式時間算法的問題的集合 NP =? P：是計算機(jī)科學(xué)中非常重要而又經(jīng)歷了幾十年始終未解決的一個問題 它的解決可導(dǎo)致一系列理論問題的解決,7,

5、基 本 知 識,算法分析 確定執(zhí)行一個算法需要消耗的計算資源的數(shù)量的分析過程 算法的效率或復(fù)雜度表示為一個函數(shù)，其定義域是輸入數(shù)據(jù)的規(guī)模（長度，算法大都設(shè)計成允許任意長的輸入），值域通常是執(zhí)行步數(shù)（時間復(fù)雜度）或所需存儲空間數(shù)量（空間復(fù)雜度） 在算法的理論分析中，通常是估計算法漸近意義上的復(fù)雜度 精確分析算法的復(fù)雜度有時也可行，但它通?；谝恍┡c具體實現(xiàn)相關(guān)的假設(shè),8,基 本 知 識,可計算性、計算復(fù)雜性和算法分析的區(qū)別 算法分析致力于分析求解一個問題的某個具體算法所需的資源量 計算復(fù)雜性理論關(guān)注的是用所有可能算法解決同一類問題層面上的一般性議題 可計算性理論關(guān)注的是原則上可以用算法求解的問題

6、（把問題區(qū)分為可計算和不可計算） 資源受限和不受限是區(qū)分計算復(fù)雜性理論和可計算性理論的一個重要標(biāo)志,9,復(fù)雜性的計量,兩種查找算法的效率比較 int search(int val) / 順序查找 int j = 0; /int am無重復(fù)且已按從小到大排序 while(aj val / 在最壞情況下，需要把val與a的所有分量比較,10,復(fù)雜性的計量,兩種查找算法的效率比較 int search(int val) / 二分查找 int i, j, k; /int am無重復(fù)且已按從小到大排序 i = 0; j = m 1; while(i = ak) i = k + 1; if (j i =

7、1) return 1; else return k; / 在最壞情況下，只需要把val與a的log2 m個 / 分量比較，顯然效率高于前一個算法,11,復(fù)雜性的計量,兩種求斐波那契數(shù)列前n+1項算法的效率比較 void Fibonacci(int n) / 假定n = 0，遞歸算法 int i; for (i = 0; i = n; i+) printf(“%dn”, fib(n); int fib(int k) if (k = 0) return 0; else if (k = 1) return 1; else return fib(k 1) + fib(k 2); 對該數(shù)列a0, a1

8、, , an, ak(0 k n)被重復(fù)計算多次,12,復(fù)雜性的計量,兩種求斐波那契數(shù)列前n+1項算法的效率比較 void Fibonacci(int n) / 假定n = 0，循環(huán)算法 int j0, j1, i, temp; j0 = 0; j1 = 1; for(i = 0; i = n; i +) printf(“%dn”, j0); temp = j1; j1 = j0 + j1; j0 = temp; ak(0 k n)都只計算1次, 顯然效率高于前一個算法,13,復(fù)雜性的計量,兩種求斐波那契數(shù)列前n+1項算法的效率比較 void Fibonacci(int n) / 假定n =

9、0，循環(huán)算法 int j0, j1, i, temp; j0 = 0; j1 = 1; for(i = 0; i = n; i +) printf(“%dn”, j0); temp = j1; j1 = j0 + j1; j0 = temp; 這種比較單純反映作為算法精髓的計算方法本身 的效率，不涉及運行這些算法的實際計算機(jī)的性能,14,復(fù)雜性的計量,復(fù)雜性函數(shù) 時間和空間復(fù)雜性函數(shù)分別是：T(N, I)和S(N, I) N：問題規(guī)模， I：算法的輸入 問題問題的規(guī)模N 在數(shù)組中查找值為val的分量數(shù)組中分量個數(shù) 矩陣相乘矩陣的階 數(shù)表的排序數(shù)表中的項數(shù) 遍歷二叉樹樹中節(jié)點數(shù) 求數(shù)列的前n項項

10、數(shù)n 解有關(guān)圖的問題圖中節(jié)點數(shù)或邊數(shù),15,復(fù)雜性的計量,復(fù)雜性函數(shù) 時間和空間復(fù)雜性函數(shù)分別是：T(N, I)和S(N, I) N：問題規(guī)模， I：算法的輸入 時間復(fù)雜性和空間復(fù)雜性的概念類同，計算方法 相似，且空間復(fù)雜性分析相對簡單，因此下面僅討 論時間復(fù)雜性 若抽象計算機(jī)有k種元運算，它們所需時間依次為 t1, t2, , tk。若某算法用到這k種運算的次數(shù)依次是 e1, e2, , ek，ei(1 i k)是N和I的函數(shù), ei =ei (N, I), 則T(N, I) = ti ei (N, I,16,復(fù)雜性的計量,復(fù)雜性函數(shù) 有關(guān)算法的輸入I 不可能為規(guī)模為N的每一種合法輸入I 都

11、去統(tǒng)計 ei (N, I) 簡化辦法：在規(guī)模為N的某些或某類有代表性的合法輸入中統(tǒng)計相應(yīng)的ei ，評價這些情況下的時間復(fù)雜性,17,復(fù)雜性的計量,三種時間復(fù)雜性函數(shù) 最壞情況 Tmax(N) = max T(N, I) = ti ei (N, I) = T(N, I) 其中DN為規(guī)模為N的合法輸入集, I是達(dá)max的輸入 最好情況（其中I是達(dá)min的輸入） Tmin(N) = min T(N, I) = ti ei (N, I) = T(N, I) 平均情況 Tavg(N) = P(I) T(N, I) = P(I) ti ei (N, I) 其中P(I)是在算法的應(yīng)用中出現(xiàn)輸入I的概率,ID

12、N,IDN,IDN,IDN,max ti ei (N, I,IDN,18,復(fù)雜性的漸近行為及其階,如何簡化算法分析 計算機(jī)解決的問題越來越復(fù)雜，規(guī)模越來越大 若按先前介紹的方法，把所有的元計算都考慮進(jìn)去，并進(jìn)行精確分析，則算法分析的步驟之多，工作量之大，令人難以承受 下面介紹復(fù)雜性漸近行為的概念，以簡化算法分析,19,復(fù)雜性的漸近行為及其階,復(fù)雜性的漸近行為（asymptotic behavior） 對于算法A的T(N)，一般來說，當(dāng)N單調(diào)遞增且趨 于時， T(N)也單調(diào)遞增且趨于 對于T(N)，若存在T(N)，使得當(dāng)N 時有 (T(N) T(N) / T(N) 0 則稱T(N)是T(N)當(dāng)N

13、 時的漸近行為，或稱T(N) 為算法A的、當(dāng)N 時的漸近復(fù)雜性 直觀上， T(N)是T(N)略去低項后的主項 例：若T(N)是3N2+4Nlog2N+7時，T(N)可以是3N2, 若N ，(4Nlog2N+7)/(3N2+4Nlog2N+7) 0,N2稱為階,20,復(fù)雜性的漸近行為及其階,復(fù)雜性的漸近行為 對于T(N)，若存在T(N)，使得當(dāng)N 時有 (T(N) T(N) / T(N) 0 則稱T(N)為算法A的當(dāng)N 時的漸近復(fù)雜性 若用T(N)代替T(N)，作為算法A在N 時的復(fù)雜 性的度量，則復(fù)雜性分析明顯簡化 復(fù)雜性分析的目的：在于比較同一問題的不同算 法的效率，若兩個算法的階不同，則可

14、知誰效率高,21,復(fù)雜性的漸近行為及其階,復(fù)雜性的漸近行為 對于T(N)，若存在T(N)，使得當(dāng)N 時有 (T(N) T(N) / T(N) 0 則稱T(N)為算法A的當(dāng)N 時的漸近復(fù)雜性 簡化T(N)分析：只需關(guān)心T(N)的階，把其常數(shù)因 子忽略。如在3N2中，不用關(guān)心系數(shù) 3 進(jìn)一步簡化T(N)分析：假設(shè)算法中用到的所有不 同的元運算執(zhí)行一次都只需一個時間單位,22,復(fù)雜性的漸近行為及其階,算法復(fù)雜性的漸近分析方法 只要考察當(dāng)問題規(guī)模充分大時，算法復(fù)雜性在漸近意義下的階。算法分析通常都是這么做的 與此簡化的復(fù)雜性分析相配套，需要引入一些漸近意義下的記號,23,復(fù)雜性的漸近行為及其階,漸近意

15、義下的記號O（代表order of ） 若f 和g是正整數(shù)集上的正函數(shù)，若存在大于0的常 數(shù)C和自然數(shù)N0，使得N N0時有f(N) Cg(N), 則 稱：在N充分大時，Cg(N)是函數(shù)f(N)的一個上界， 記為f(N) = O(g(N)，并簡稱f(N)不大于g(N)的階 使用“=”是不妥的，這是一種對“=”的濫用 f(N) = O(g(N)作為一個整體，表達(dá)函數(shù)f 和g的一種關(guān)系 “=”在這里的含義是什么？ 單獨的O(g(N)記號的含義是什么,24,復(fù)雜性的漸近行為及其階,漸近意義下的記號O（代表order of ） 若f 和g是正整數(shù)集上的正函數(shù)，若存在大于0的常 數(shù)C和自然數(shù)N0，使得N

16、 N0時有f(N) Cg(N), 則 稱：在N充分大時，Cg(N)是函數(shù)f(N)的一個上界， 記為f(N) = O(g(N)，并簡稱f(N)不大于g(N)的階 Intuitively this notation groups functions according to their growth respective to some parameter; as such, the notation is abusive in two respects: It abuses =, and it invokes terms that are real numbers instead of func

17、tion terms. 見/wiki/ Abuse_of_notation#Big_O_notation(網(wǎng)頁已被刪去,25,復(fù)雜性的漸近行為及其階,漸近意義下的記號O（代表order of ） 若f 和g是正整數(shù)集上的正函數(shù)，若存在大于0的常 數(shù)C和自然數(shù)N0，使得N N0時有f(N) Cg(N), 則 稱：在N充分大時，Cg(N)是函數(shù)f(N)的一個上界， 記為f(N) = O(g(N)，并簡稱f(N)不大于g(N)的階 千萬不要把這里的“=”理解成左右兩邊相等 對于函數(shù)g(N)，盡可能使用簡單的解析式。例如 N, N2等 N. N 1 3N

18、4N, 故 f(N) = O(N) (f(N) = 3N, g(N) = N, C =4, 下面略去f和g的定義,26,復(fù)雜性的漸近行為及其階,漸近意義下的記號O（代表order of ） 若f 和g是正整數(shù)集上的正函數(shù)，若存在大于0的常 數(shù)C和自然數(shù)N0，使得N N0時有f(N) Cg(N), 則 稱：在N充分大時，Cg(N)是函數(shù)f(N)的一個上界， 記為f(N) = O(g(N)，并簡稱f(N)不大于g(N)的階 N. N 10 2N2+11N 10 3N2， 故 2N2+11N 10 = O(N2) N. N 1 N+1024 1025N, 故 N+1024 = O(N) N. N 1

19、 N2 N3，故N2 = O(N3,27,復(fù)雜性的漸近行為及其階,漸近意義下的記號O（代表order of ） 若f 和g是正整數(shù)集上的正函數(shù)，若存在大于0的常 數(shù)C和自然數(shù)N0，使得N N0時有f(N) Cg(N), 則 稱：在N充分大時，Cg(N)是函數(shù)f(N)的一個上界， 記為f(N) = O(g(N)，并簡稱f(N)不大于g(N)的階 N3 O(N2)（使用“”也是一種濫用） 若不是這樣，則存在大于0的常數(shù)C和自然數(shù)N0 , 使得N N0時有N3 CN2，即N C 取N = max(N0 , C +1)時，該不等式不成立，故 N3 O(N2,28,復(fù)雜性的漸近行為及其階,順序查找算法回

20、顧 int search(int val) / 順序查找 int j = 0; / int am不重復(fù)且已按從小到大排序 while(aj val,若賦值、比較和返回執(zhí)行一次所需時間分別是a, t和r，若val 等于a0，則Tmin(m) = a + 2t + r，其中m是問題規(guī)模,29,復(fù)雜性的漸近行為及其階,漸近意義下的記號O（代表order of ） 若f 和g是正整數(shù)集上的正函數(shù)，若存在大于0的常 數(shù)C和自然數(shù)N0，使得N N0時有f(N) Cg(N), 則 稱：在N充分大時，Cg(N)是函數(shù)f(N)的一個上界， 記為f(N) = O(g(N)，并簡稱f(N)不大于g(N)的階 對于順

21、序查找算法，在最好情況下，只要取 C = a + 2t + r，就有Tmin(m) C 1， 因此有Tmin(m) Cg(m)，其中g(shù)(m) = 1， 即Tmin(m) = O(1,30,復(fù)雜性的漸近行為及其階,例：估計下面二重循環(huán)的最壞時間復(fù)雜性的階 for(i = 1; i N; i+) for(j = 1; j i; j+) s1; s2; s3; s4; 其中sk(k =1, 2, 3, 4)都是賦值語句 對內(nèi)循環(huán)體，執(zhí)行一次需要的時間是4a 加上循環(huán)控制，則是5a + t 內(nèi)循環(huán)執(zhí)行i 次, 需時間(5a +t) i, 因此上界為 O(i) 外循環(huán)執(zhí)行N次，需時間 (5a +t) (

22、1+2+ +N) + (a + t) N,31,復(fù)雜性的漸近行為及其階,例：估計下面二重循環(huán)的最壞時間復(fù)雜性的階 for(i = 1; i N; i+) for(j = 1; j i; j+) s1; s2; s3; s4; 其中sk(k =1, 2, 3, 4)都是賦值語句 外循環(huán)執(zhí)行N次，需時間 (5a +t) N(N+1)/2 + (a +t) N 因此上界為O(N2) 這是規(guī)模充分大時的上界 這個上界的階越低，則評估就越精確，結(jié)果就越有價值,32,復(fù)雜性的漸近行為及其階,關(guān)于記號O(g(N)的討論 當(dāng)討論復(fù)雜算法上界時，很希望上界記號O(g(N) 能參與到復(fù)雜性計算中 例如，上例內(nèi)循環(huán)

23、的上界O(i)，則累加起來便是外循環(huán)的時間復(fù)雜性 T(N) = O(i) = O(i) = O(N(N+1)/2) = O(N2) 若希望如此，則需要有一些演算規(guī)則，并證明其正確性,33,復(fù)雜性的漸近行為及其階,關(guān)于記號O(g(N)的討論 記號O的運算規(guī)則（某書給出） O(f(N) + O(g(N) = O(max(f(N), g(N) O(f(N) + O(g(N) = O(f(N) + g(N) O(f(N) O(g(N) = O(f(N) g(N) 問題：在O()未定義時，等號左邊+和的含義,f(N), 若f(N) g(N) 其中max(f(N) , g(N) = g(N), 若f(N)

24、 g(N,34,復(fù)雜性的漸近行為及其階,關(guān)于記號O(g(N)的討論 一種解釋（另一本書給出）：O(g(N) = f(N) | C 0.N0 0.N N0. 0 f(N) Cg(N) 符號O(g(N) 在此給出了明確的數(shù)學(xué)意義 寫f(N) O(g(N)容易理解( 而不是f(N) = O(g(N) ) 但解釋O(f(N) + O(g(N) 和O(f(N) O(g(N)中的+和（尤其是 ）仍然有困難 導(dǎo)致各書仍繼續(xù)使用f(N) = O(g(N)記號，使得讀者難理解,35,復(fù)雜性的漸近行為及其階,其他漸近意義下的記號 下界記號 若f 和g是正整數(shù)集上的正函數(shù)，若存在大于0的常 數(shù)C和自然數(shù)N0，使得N

25、 N0時有f(N) Cg(N), 則 稱：在N充分大時，Cg(N)是函數(shù)f(N)的一個下界，記為f(N) = (g(N)，并簡稱f(N)不小于g(N)的階 記號 f(N) =(g(N) f(N) = O(g(N) f(N) =(g(N) 此時稱f(N)和g(N)同階 還有其他記號,36,復(fù)雜性的漸近行為及其階,算法與漸近時間復(fù)雜性的關(guān)系 算法 漸近復(fù)雜 在C1上可 在C2上可 N1和N2的關(guān)系 性T(N) 解規(guī)模N1 解規(guī)模N2 方程Ti(N2i)=10Ti(N1i)是求解N2i和N1i之間的關(guān)系 等式Ti(N2i)=10Ti(N1i)的含義是：第i個算法在C1上運行10倍于C2上運行的時間，

26、則等號兩邊效果一樣 同一問題六個算法, 在C1和C2上運行, C2的速度是C1 10倍. 從Ti(N2i)=10Ti(N1i)(i =1, , 6)解出關(guān)系式,37,復(fù)雜性的漸近行為及其階,算法與漸近時間復(fù)雜性的關(guān)系 算法 漸近復(fù)雜 在C1上可 在C2上可 N1和N2的關(guān)系 性T(N) 解規(guī)模N1 解規(guī)模N2 A1 N N11 N21 N21 = 10N11 A2 NlogN N12 N22 N22 10N12 A3 N2 N13 N23 N23 = 10N13 A4 N3 N14 N24 N24 = 10N14 A5 2N N15 N25 N25 = N15+ log10 A6 N! N16 N26 N26=N16+小的常數(shù) 同一問題六個算法, 在C1和C2上運行, C2的速度是C1 10倍. 從Ti(N2i)=10Ti(N1i)(i =1, , 6)解出關(guān)系式見上表,38,復(fù)雜性的漸近行為及其階,復(fù)雜性漸近分析的重要性 對于低效算法，計算機(jī)速度數(shù)10