《算法設(shè)計(jì)與分析》第02章

1、算法設(shè)計(jì)與分析DeSign and Analysis of AlgorithmsIn C+“十一五”國(guó)家級(jí)規(guī)劃教材 陳慧南 編著電子工業(yè)出版社 第2章 算法分析基礎(chǔ)2.1 算法復(fù)雜度 2.2 漸近表示法 2.3 遞推關(guān)系2.4 分?jǐn)偡治?2.1 算法復(fù)雜度 2.1.1 什么是好的算法 好的算法 一個(gè)好的算法應(yīng)具有以下4個(gè)重要特性:正確性（correctness）：算法的執(zhí)行結(jié)果應(yīng)當(dāng)滿足預(yù)先規(guī)定的功能和性能要求。簡(jiǎn)明性（simplicity）：算法應(yīng)思路清晰、層次分明、容易理解、利于編碼和調(diào)試。效率（efficiency）：算法應(yīng)有效使用存儲(chǔ)空間，并具有高的時(shí)間效率。最優(yōu)性（optimality

2、）：算法的執(zhí)行時(shí)間已達(dá)到求解該類問(wèn)題所需時(shí)間的下界。 程序健壯性是指當(dāng)輸入不合法數(shù)據(jù)時(shí)，程序應(yīng)能做適當(dāng)處理而不至于引起嚴(yán)重后果。其含義是：當(dāng)程序萬(wàn)一遇到意外時(shí)，能按某種預(yù)定方式做出適當(dāng)處理。正確性和健壯性是相互補(bǔ)充的。 2.1.2 影響程序運(yùn)行時(shí)間的因素影響程序運(yùn)行時(shí)間的因素主要有：程序所依賴的算法；問(wèn)題規(guī)模和輸入數(shù)據(jù)；計(jì)算機(jī)系統(tǒng)性能。 2.1.3 算法的時(shí)間復(fù)雜度 抽象機(jī)模型設(shè)抽象機(jī)提供由m個(gè)基本運(yùn)算（也可稱為語(yǔ)句）組成的運(yùn)算集O = O1, O2, , Om，每個(gè)運(yùn)算都是基本的，它們的執(zhí)行時(shí)間是有限常量。同時(shí)設(shè)執(zhí)行第i個(gè)運(yùn)算Oi所需的時(shí)間是i，1im。 時(shí)間復(fù)雜度一個(gè)算法的時(shí)間復(fù)雜度（ti

3、me complexity）是指算法運(yùn)行所需的時(shí)間。設(shè)有一個(gè)在抽象機(jī)上運(yùn)行的算法A，I是某次運(yùn)行時(shí)的輸入數(shù)據(jù)，其規(guī)模為n，則算法A的運(yùn)行時(shí)間T是n和I的函數(shù)，記做T(n, I)。又設(shè)在該次運(yùn)算中抽象機(jī)的第i個(gè)基本運(yùn)算Oi的執(zhí)行次數(shù)為i，1im，i也是n和I的函數(shù)，記做i(n, I)。 對(duì) I, n，i(n, I) ，1im 那么，算法A在輸入為I時(shí)的運(yùn)行時(shí)間是： 最好、最壞和平均時(shí)間復(fù)雜度最好時(shí)間復(fù)雜度最壞時(shí)間復(fù)雜度平均時(shí)間復(fù)雜度Dn指規(guī)模為n的所有合法輸入的集合 2.1.4 使用程序步分析算法 一個(gè)程序步（program step）是指在語(yǔ)法上或語(yǔ)義上有意義的程序段，該程序段的執(zhí)行時(shí)間必須與

4、問(wèn)題實(shí)例的規(guī)模無(wú)關(guān)。 例子 【程序2-1】 求數(shù)組元素累加之和的迭代程序float Sum(float list, const int n) float tempsum=0.0; count +; /針對(duì)賦值語(yǔ)句 for (int i=0; in) Swap(m,n);while(m0)int c=n%m; n=m; m=c;return n;定理2-2 2.1.5 算法的空間復(fù)雜度 一個(gè)算法的空間復(fù)雜度（space complexity）是指算法運(yùn)行所需的存儲(chǔ)空間。 程序運(yùn)行所需的存儲(chǔ)空間包括以下兩部分：固定空間需求（fixed space requirement）這部分空間與所處理數(shù)據(jù)的大

5、小和個(gè)數(shù)無(wú)關(guān)，也就是說(shuō)，與問(wèn)題實(shí)例的特征無(wú)關(guān)。 可變空間需求（variable space requirement）這部分空間大小與算法在某次執(zhí)行中處理的特定數(shù)據(jù)的規(guī)模有關(guān)。 練習(xí)分析程序1-6（漢諾塔問(wèn)題）的程序步數(shù) n0void Hanoi(int n, tower x, tower y, tower z) if (n) Hanoi(n-1, x, z, y); Move(n,x,y); Hanoi(n-1, z, y, x); 2.2 漸近表示法 程序步的精確計(jì)算數(shù)量級(jí)估計(jì) 2.2.1 大O記號(hào)定義2-1 設(shè)函數(shù)f(n)和g(n)是定義在非負(fù)整數(shù)集合上的正函數(shù)，如果存在兩個(gè)正常數(shù)c和n0

6、，使得當(dāng)nn0時(shí)，有f(n)cg(n)，則記做f(n) = O(g(n)，稱為大O記號(hào)（big Oh notation）。 例2-1 f(n) = 2n + 3 = O(n)當(dāng)n3時(shí)，2n+33n，所以，可選c = 3，n0 = 3。對(duì)于nn0，f(n) = 2n + 33n，所以，f(n) = O(n)，即2n + 3O(n)。這意味著，當(dāng)n3時(shí)，程序2-1的程序步不會(huì)超過(guò)3n，2n + 3 = O(n)。 例2-2 f(n) = 10n2 + 4n + 2 = O(n2)對(duì)于n2時(shí)，有10n2 + 4n + 210n2 + 5n，并且當(dāng)n5時(shí)，5nn2，因此，可選c = 11, n0 =

7、5；對(duì)于nn0，f(n) = 10n2 + 4n + 211n2，所以f(n) = O(n2)。 例2-3 f(n) = n！= O(nn)對(duì)于n1，有n(n 1)(n 2) 1nn，因此，可選c = 1，n0 = 1。對(duì)于nn0，f(n) = n！nn，所以，f(n) = O(nn)。 例2-3 10n2 + 9 O(n)使用反證法，假定存在c和n0，使得對(duì)于nn0，10n2 + 9cn始終成立，那么有10n + 9/nc，即nc/10 9/(10n)總成立。但此不等式不可能總成立，取n = c/10 + 1時(shí)，該不等式便不再成立。 定理2-1 如果f(n) = amnm + am1nm1

8、+ + a1n + a0是m次多項(xiàng)式，且am0，則f(n) = O(nm)。證明：取n0 = 1，當(dāng)nn0時(shí)，有 f(n)= amnm + am1nm1 + + a1n + a0 |am|nm + |am1|nm1 + + |a1|n + |a0| (|am| + |am1|/n + + |a1|/nm1 + |a0|/nm) nm (|am| + |am1| + + |a1| + |a0|) nm可取c= |am| + |am1| + + |a1| + |a0|，定理得證。 漸近時(shí)間復(fù)雜度 使用大O記號(hào)及下面定義的幾種漸近表示法表示的算法時(shí)間復(fù)雜度，稱為算法的漸近時(shí)間復(fù)雜度（asymptot

9、ic complexity）。 O(1)常數(shù)級(jí)時(shí)間復(fù)雜度只要適當(dāng)選擇關(guān)鍵操作，算法的漸近時(shí)間復(fù)雜度可以由關(guān)鍵操作的執(zhí)行次數(shù)之和來(lái)計(jì)算。一般地，關(guān)鍵操作的執(zhí)行次數(shù)與問(wèn)題的規(guī)模有關(guān)，是n的函數(shù)。 【程序2-3】 矩陣乘法for（i=0; in; i+） /n+1 for（j=0; jn; j+） /n(n+1) cij=0; /n2 for（k=0; kn; k+） /n2(n+1) cij+=aik*bkj; /n3 2.2.2 記號(hào)定義2-2 設(shè)有函數(shù)f(n)和g(n)是定義在非負(fù)整數(shù)集合上的正函數(shù)，如果存在兩個(gè)正常數(shù) c和n0，使得當(dāng)nn0時(shí)，有f(n)c g(n)，則記做f(n) = (g

10、(n)，稱為記號(hào)（omega notation）。 例2-5 f(n) = 2n + 3 = (n)對(duì)所有n，2n+32n，可選c = 2，n0=0。對(duì)于nn0，f(n) = 2n+32n，所以，f(n) = (n)，即2n + 3(n)。 例2-6 f(n) = 10n2 + 4n + 2 = (n2)對(duì)所有n，10n2 + 4n + 210n2，可選c = 10，n0 = 0。對(duì)于nn0，f(n) = 10n2 + 4n + 210n2，所以，f(n) = (n2)。 定理2-3 如果f(n) = amnm + am1nm1 + + a1n + a0是m次多項(xiàng)式，且am0，則f(n) =

11、(nm)。 2.2.3 記號(hào)定義2-3 設(shè)有函數(shù)f(n)和g(n)是定義在非負(fù)整數(shù)集合上的正函數(shù)，如果存在正常數(shù)c1，c2和n0，使得當(dāng)nn0時(shí)，有c1 g(n)f(n)c2 g(n)，則記做f(n) = (g(n)，稱為記號(hào)（Theta notation）。 例2-7 f(n) = 2n + 3 = (n)，即2n + 3(n)。例2-8 f(n) = 10n2 + 4n + 2 = (n2)。 定理2-4 如果f(n) = amnm + am1nm1 + + a1n + a0是m次多項(xiàng)式，且am0，則f(n) = (nm)。 2.2.4 小o記號(hào)定義2-4 f(n) = o(g(n)當(dāng)且僅

12、當(dāng)f(n) = O(g(n)且f(n) (g(n)例2-9 f(n)=2n+3=o(n2)，即2n+3o(n2)。 2.2.5 算法按時(shí)間復(fù)雜度分類算法按計(jì)算時(shí)間分類凡漸近時(shí)間復(fù)雜度有多項(xiàng)式時(shí)間限界的算法稱做多項(xiàng)式時(shí)間算法（polynomial time algorithm），而漸近時(shí)間復(fù)雜度為指數(shù)函數(shù)限界的算法稱做指數(shù)時(shí)間算法（exponential time algorithm）。 最常見(jiàn)的多項(xiàng)式時(shí)間算法的漸近時(shí)間復(fù)雜度 O(1)O(log n)O(n)O(nlog n)O(n2)O(n3)最常見(jiàn)的指數(shù)時(shí)間算法的漸近時(shí)間復(fù)雜度 O(2n)O(n！)O(nn) 算法時(shí)間分析的目的是為了設(shè)法降

13、低時(shí)間復(fù)雜度的數(shù)量級(jí)！ 2.3 遞推關(guān)系 2.3.1 遞推方程遞推方程（recurrence equation）是自然數(shù)上一個(gè)函數(shù)T(n)，它使用一個(gè)或多個(gè)小于n時(shí)的值的等式或不等式來(lái)描述。遞推方程也稱為遞推關(guān)系或遞推式。 遞推方程必須有一個(gè)初始條件（也稱邊界條件）。 例2-10 程序1-5的時(shí)間分析 設(shè)n = d1d2dk是k位數(shù)，當(dāng)k = 1時(shí)，只執(zhí)行cout語(yǔ)句和if判定語(yǔ)句；當(dāng)n至少是2位數(shù)（k1）時(shí)，除了執(zhí)行這兩個(gè)操作外，還需執(zhí)行遞歸函數(shù)調(diào)用PrintDigit(n/10)，n/10是k 1位數(shù) 。 計(jì)算遞推公式的三種方法迭代法替換法主方法 1 迭代方法迭代方法的思想是擴(kuò)展遞推式，將

14、遞推式先轉(zhuǎn)換成一個(gè)和式，然后計(jì)算該和式，得到漸近復(fù)雜度。T(k) = 2k = (k) 例2-12 使用迭代方法分析程序1-6。函數(shù)Hanoi中兩次調(diào)用自身，函數(shù)調(diào)用使用的實(shí)在參數(shù)均為n 1，函數(shù)Move所需時(shí)間具有常數(shù)界(1)，可以將其視為一個(gè)程序步，于是有： 擴(kuò)展并計(jì)算此遞推式：T(n) = 2T(n 1) + 1 = 2(2T(n 2) + 1) + 1 = 22T(n 2) + 2 + 1= 23T(n 3) + 22 + 2 + 1= 2n1T(1) + + 22 + 2 + 1= 2n1 + + 22 + 2 + 1 = 2n 1 使用遞歸樹（recursion tree）可以形象

15、地看到遞推式的迭代過(guò)程。 例2-13 T(n) = 2T(n/2) + n的遞歸樹遞歸樹 例2-14 T(n) = T(n/3) + T(2n/3) + n的遞歸樹 2 替換方法替換方法要求首先猜測(cè)遞推式的解，然后用歸納法證明。例2-11 使用替換方法分析程序1-6?？梢韵葘?duì)以下這些小的示例進(jìn)行計(jì)算：T(1)=1, T(2)=1+1+1=3,T(3) = 7 = 23 1；T(4) = 15 = 24 1；T(5) = 31 = 25 1；T(6) = 63 = 26 1看起來(lái)，似乎T(n) = 2n 1，n1。 證明：（歸納法證明）當(dāng)n = 1時(shí)，T(1) = 1，結(jié)論成立。歸納法假設(shè)：當(dāng)k

16、n時(shí)，有T(k) = 2k 1，那么，當(dāng)k = n時(shí)，T(n) = 2T(n 1) + 1 = 2(2n1 1) + 1 = 2n 1。因此，對(duì)所有n1，T(n) = 2n 1 = (2n)。 2.3.4 主方法 主方法在遞歸算法分析中，常需要求解如下形式的遞推式：T(n) = aT(n/b) + f(n) 式中，a1和b1是常數(shù)，f(n)是一個(gè)漸近正函數(shù)，n/b指n/b 或 n/b。 求解這類遞推式的方法稱為主方法。 定理2-5 （主定理）設(shè)a1和b1為常數(shù)，f(n)是一個(gè)函數(shù)，T(n)由下面的遞推式定義T(n) = aT(n/b) + f(n)式中，n/b指n/b 或 n/b，則T(n)有

17、如下的漸近界：（1）若對(duì)某常數(shù)0，有f(n) = O( nlogba - )，則T(n) = (nlogba)；（2）若f(n) = (nlogba)，則T(n) = (nlogba log n)；（3）若對(duì)某常數(shù)0，有f(n) = (nlogba + )，且對(duì)某個(gè)常數(shù)c1和所有足夠大的n，有af(n/b)cf(n)，則T(n) = (f(n)。 例2-15 T(n) = 16T(n/4) + n因?yàn)閍 = 16, b = 4, = n2, f(n) = n = O(nlogba - ) = O(n2)，其中， = 1與主定理的情況（1）相符合，T(n) = () = (n2)。例2-16 T(n) = T(3n/7) + 1因?yàn)閍 = 1, b = 7/3, nlogba = nlog7/31 = n0 = 1, f(n) = 1 = (nlogba)，所以，符合主定理情況（2），T(n) = (nlogba logn) = (logn)。例2-17 T(n) = 3T(n/4) + n logn因?yàn)閍 = 3, b = 4, nlogba = nlog43 = O(n0.793), f(n) = nlogn = (nlogba + )，其中，0.2。由于對(duì)足夠大的n，3(n/4)log(n/4)(3/4)nlogn，這里c = 3/4，符合主定理情