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

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

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

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

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

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

6、（把問(wèn)題區(qū)分為可計(jì)算和不可計(jì)算） 資源受限和不受限是區(qū)分計(jì)算復(fù)雜性理論和可計(jì)算性理論的一個(gè)重要標(biāo)志,9,復(fù)雜性的計(jì)量,兩種查找算法的效率比較 int search(int val) / 順序查找 int j = 0; /int am無(wú)重復(fù)且已按從小到大排序 while(aj val / 在最壞情況下，需要把val與a的所有分量比較,10,復(fù)雜性的計(jì)量,兩種查找算法的效率比較 int search(int val) / 二分查找 int i, j, k; /int am無(wú)重復(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個(gè) / 分量比較，顯然效率高于前一個(gè)算法,11,復(fù)雜性的計(jì)量,兩種求斐波那契數(shù)列前n+1項(xiàng)算法的效率比較 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); 對(duì)該數(shù)列a0, a1

8、, , an, ak(0 k n)被重復(fù)計(jì)算多次,12,復(fù)雜性的計(jì)量,兩種求斐波那契數(shù)列前n+1項(xiàng)算法的效率比較 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)都只計(jì)算1次, 顯然效率高于前一個(gè)算法,13,復(fù)雜性的計(jì)量,兩種求斐波那契數(shù)列前n+1項(xiàng)算法的效率比較 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ì)算方法本身 的效率，不涉及運(yùn)行這些算法的實(shí)際計(jì)算機(jī)的性能,14,復(fù)雜性的計(jì)量,復(fù)雜性函數(shù) 時(shí)間和空間復(fù)雜性函數(shù)分別是：T(N, I)和S(N, I) N：?jiǎn)栴}規(guī)模， I：算法的輸入 問(wèn)題問(wèn)題的規(guī)模N 在數(shù)組中查找值為val的分量數(shù)組中分量個(gè)數(shù) 矩陣相乘矩陣的階 數(shù)表的排序數(shù)表中的項(xiàng)數(shù) 遍歷二叉樹樹中節(jié)點(diǎn)數(shù) 求數(shù)列的前n項(xiàng)項(xiàng)

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

11、去統(tǒng)計(jì) ei (N, I) 簡(jiǎn)化辦法：在規(guī)模為N的某些或某類有代表性的合法輸入中統(tǒng)計(jì)相應(yīng)的ei ，評(píng)價(jià)這些情況下的時(shí)間復(fù)雜性,17,復(fù)雜性的計(jì)量,三種時(shí)間復(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ù)雜性的漸近行為及其階,如何簡(jiǎn)化算法分析 計(jì)算機(jī)解決的問(wèn)題越來(lái)越復(fù)雜，規(guī)模越來(lái)越大 若按先前介紹的方法，把所有的元計(jì)算都考慮進(jìn)去，并進(jìn)行精確分析，則算法分析的步驟之多，工作量之大，令人難以承受 下面介紹復(fù)雜性漸近行為的概念，以簡(jiǎn)化算法分析,19,復(fù)雜性的漸近行為及其階,復(fù)雜性的漸近行為（asymptotic behavior） 對(duì)于算法A的T(N)，一般來(lái)說(shuō)，當(dāng)N單調(diào)遞增且趨 于時(shí)， T(N)也單調(diào)遞增且趨于 對(duì)于T(N)，若存在T(N)，使得當(dāng)N 時(shí)有 (T(N) T(N) / T(N) 0 則稱T(N)是T(N)當(dāng)N

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

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

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

16、 N0時(shí)有f(N) Cg(N), 則 稱：在N充分大時(shí)，Cg(N)是函數(shù)f(N)的一個(gè)上界， 記為f(N) = O(g(N)，并簡(jiǎ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)頁(yè)已被刪去,25,復(fù)雜性的漸近行為及其階,漸近意義下的記號(hào)O（代表order of ） 若f 和g是正整數(shù)集上的正函數(shù)，若存在大于0的常 數(shù)C和自然數(shù)N0，使得N N0時(shí)有f(N) Cg(N), 則 稱：在N充分大時(shí)，Cg(N)是函數(shù)f(N)的一個(gè)上界， 記為f(N) = O(g(N)，并簡(jiǎn)稱f(N)不大于g(N)的階 千萬(wàn)不要把這里的“=”理解成左右兩邊相等 對(duì)于函數(shù)g(N)，盡可能使用簡(jiǎ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ù)雜性的漸近行為及其階,漸近意義下的記號(hào)O（代表order of ） 若f 和g是正整數(shù)集上的正函數(shù)，若存在大于0的常 數(shù)C和自然數(shù)N0，使得N N0時(shí)有f(N) Cg(N), 則 稱：在N充分大時(shí)，Cg(N)是函數(shù)f(N)的一個(gè)上界， 記為f(N) = O(g(N)，并簡(jiǎ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ù)雜性的漸近行為及其階,漸近意義下的記號(hào)O（代表order of ） 若f 和g是正整數(shù)集上的正函數(shù)，若存在大于0的常 數(shù)C和自然數(shù)N0，使得N N0時(shí)有f(N) Cg(N), 則 稱：在N充分大時(shí)，Cg(N)是函數(shù)f(N)的一個(gè)上界， 記為f(N) = O(g(N)，并簡(jiǎn)稱f(N)不大于g(N)的階 N3 O(N2)（使用“”也是一種濫用） 若不是這樣，則存在大于0的常數(shù)C和自然數(shù)N0 , 使得N N0時(shí)有N3 CN2，即N C 取N = max(N0 , C +1)時(shí)，該不等式不成立，故 N3 O(N2,28,復(fù)雜性的漸近行為及其階,順序查找算法回

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

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

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

23、的上界O(i)，則累加起來(lái)便是外循環(huán)的時(shí)間復(fù)雜性 T(N) = O(i) = O(i) = O(N(N+1)/2) = O(N2) 若希望如此，則需要有一些演算規(guī)則，并證明其正確性,33,復(fù)雜性的漸近行為及其階,關(guān)于記號(hào)O(g(N)的討論 記號(hào)O的運(yùn)算規(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) 問(wèn)題：在O()未定義時(shí)，等號(hào)左邊+和的含義,f(N), 若f(N) g(N) 其中max(f(N) , g(N) = g(N), 若f(N)

24、 g(N,34,復(fù)雜性的漸近行為及其階,關(guān)于記號(hào)O(g(N)的討論 一種解釋（另一本書給出）：O(g(N) = f(N) | C 0.N0 0.N N0. 0 f(N) Cg(N) 符號(hào)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)記號(hào)，使得讀者難理解,35,復(fù)雜性的漸近行為及其階,其他漸近意義下的記號(hào) 下界記號(hào) 若f 和g是正整數(shù)集上的正函數(shù)，若存在大于0的常 數(shù)C和自然數(shù)N0，使得N

25、 N0時(shí)有f(N) Cg(N), 則 稱：在N充分大時(shí)，Cg(N)是函數(shù)f(N)的一個(gè)下界，記為f(N) = (g(N)，并簡(jiǎn)稱f(N)不小于g(N)的階 記號(hào) f(N) =(g(N) f(N) = O(g(N) f(N) =(g(N) 此時(shí)稱f(N)和g(N)同階 還有其他記號(hào),36,復(fù)雜性的漸近行為及其階,算法與漸近時(shí)間復(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個(gè)算法在C1上運(yùn)行10倍于C2上運(yùn)行的時(shí)間，

26、則等號(hào)兩邊效果一樣 同一問(wèn)題六個(gè)算法, 在C1和C2上運(yùn)行, C2的速度是C1 10倍. 從Ti(N2i)=10Ti(N1i)(i =1, , 6)解出關(guān)系式,37,復(fù)雜性的漸近行為及其階,算法與漸近時(shí)間復(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ù) 同一問(wèn)題六個(gè)算法, 在C1和C2上運(yùn)行, C2的速度是C1 10倍. 從Ti(N2i)=10Ti(N1i)(i =1, , 6)解出關(guān)系式見上表,38,復(fù)雜性的漸近行為及其階,復(fù)雜性漸近分析的重要性 對(duì)于低效算法，計(jì)算機(jī)速度數(shù)10