第1章 基礎(chǔ)知識_jlwan12

1、第1章 基礎(chǔ)知識_jlwan12程序設(shè)計程序設(shè)計分治分治策略策略動態(tài)動態(tài)規(guī)劃規(guī)劃貪心貪心算法算法 回溯與回溯與分支限界分支限界NP 完全理論完全理論近似近似算法算法隨機隨機算法算法處理難解問處理難解問題的策略題的策略算法分析與問題的計算復雜性算法分析與問題的計算復雜性算法設(shè)計技術(shù)算法設(shè)計技術(shù) 根底知識根底知識算法分析方法算法分析方法 計算復雜性理論計算復雜性理論問題處理策略問題處理策略課程主要內(nèi)容課程主要內(nèi)容第第1 1章章 根底知識根底知識 1.1 有關(guān)算法的根本概念有關(guān)算法的根本概念 算法如何表示算法如何表示 1.3 算法復雜度算法復雜度 1.4 數(shù)學根底：漸進表示法數(shù)學根底：漸進表示法 1

2、.5 遞推關(guān)系遞推關(guān)系 1.6 主定理主定理 算法是計算機科學的根底，更是程序的基石，只有具有良好的算法根底才能成為訓練有素的軟件人才。對于計算機專業(yè)的學生來說，學習算法的理由是非常充分的。因為你必須知道來自不同計算領(lǐng)域的重要算法，你也必須學會設(shè)計新的算法、確認其正確性并分析其效率。隨著計算機應(yīng)用的日益普與，各個應(yīng)用領(lǐng)域的研究和技術(shù)人員都在使用計算機求解他們各自專業(yè)領(lǐng)域的問題，他們需要設(shè)計算法，編寫程序，開發(fā)應(yīng)用軟件，所以學習算法對于越來越多的人來說變得十分必要。 1.1 有關(guān)算法的根本概念有關(guān)算法的根本概念例1：調(diào)度問題：任務(wù)集 S=1, 2, , n， 第 j 項任務(wù)加工時間: tj ,Z

3、+, j=1, 2 , n 一個可行調(diào)度方案：1, 2, , n 的排列 i1, i2, , in 求：總等待時間最少的調(diào)度方案，即求S的排列i1, i2, , in使得 nkiktkn1)1(min. 求解方法 貪心策略：加工時間短的先做 如何描述這個方法？這個方法是否對所有的實例都能得到最優(yōu)解？這個方法的效率如何？例2 排序算法的評價已有的排序算法：考察元素比較次數(shù)已有的排序算法：考察元素比較次數(shù)插入排序、冒泡排序：最壞和平均狀況下都為插入排序、冒泡排序：最壞和平均狀況下都為O(n2)快速排序：最壞狀況為快速排序：最壞狀況為O(n2)，平均狀況下為，平均狀況下為O(nlogn)堆排序、二分

4、歸并排序：最壞和平均狀況下都為堆排序、二分歸并排序：最壞和平均狀況下都為O(nlogn) 問題問題那個排序算法效率最高？那個排序算法效率最高？是否可以找到更好的算法？排序問題的計算難度如何是否可以找到更好的算法？排序問題的計算難度如何估計？估計？貨郎問題：貨郎問題： 有窮個城市的集合C = c1, c2, , cm, 距離 d(ci, cj) = d(cj, ci)Z+, 1 i 0 do2. r n mod m3. n m4. m r5. return n 實例：改進的順序檢索 算法1.2 Search(L,x)輸入：數(shù)組L1.n，其元素按照從小到大排列，數(shù) x. 輸出：假設(shè) x 在L中，輸

5、出 x 的位置下標 j；否那么輸出0. 1. j12. while jn and xLj do jj+13. if xn then j04. return j1.3 算法復雜度 算法的時間復雜度 針對問題指定根本運算，計數(shù)算法所做的根本運算次數(shù) 最壞情況下的時間復雜度 算法求解輸入規(guī)模為n的實例所需要的最長時間W(n). 平均情況下的時間復雜度 在指定輸入的概率分布下，算法求解輸入規(guī)模為n的實例所需要的平均時間 A(n). 根本概念1.3.1 什么是好的算法 好的算法 一個好的算法應(yīng)具有以下4個重要特性:1.正確性correctness：算法的執(zhí)行結(jié)果應(yīng)當滿足預先規(guī)定的功能和性能要求。2.簡明

6、性simplicity：算法應(yīng)思路清晰、層次清楚、容易理解、利于編碼和調(diào)試。3.效率efficiency：算法應(yīng)有效使用存儲空間，并具有高的時間效率。4.最優(yōu)性optimality：算法的執(zhí)行時間已到達求解該類問題所需時間的下界。 影響程序運行時間的因素主要有：程序所依賴的算法；問題規(guī)模和輸入數(shù)據(jù)；計算機系統(tǒng)性能，例如：并行集群。1.3.2 算法的時間復雜度 抽象機模型抽象機模型 設(shè)抽象機提供由設(shè)抽象機提供由m個根本運算也可稱為語個根本運算也可稱為語句組成的運算集句組成的運算集O = O1, O2, , Om，每，每個運算都是根本的，它們的執(zhí)行時間是有限常個運算都是根本的，它們的執(zhí)行時間是有限

7、常量。同時設(shè)執(zhí)行第量。同時設(shè)執(zhí)行第i個運算個運算Oi所需的時間是所需的時間是i，1im。 時間復雜度時間復雜度 一個算法的時間復雜度一個算法的時間復雜度time complexity是指算法運行所需的時間。是指算法運行所需的時間。例例 檢索問題的時間估計檢索問題的時間估計輸入：非降順序排列的數(shù)組輸入：非降順序排列的數(shù)組 L，元素數(shù)為，元素數(shù)為n； 數(shù)數(shù)x輸出：輸出： j. 假設(shè)假設(shè)x在在L中，中，j 是是 x 首次出現(xiàn)的序標；否首次出現(xiàn)的序標；否那么那么 j =0算法：算法： 順序搜索順序搜索最壞情況下時間：最壞情況下時間：W(n)=n平均情況：假設(shè)平均情況：假設(shè) xL 的概率為的概率為 p，

8、x 在在 L 不同位置不同位置等概分布等概分布. 實例集實例集 S，實例，實例IS的概率是的概率是 pI, 算法算法對對I 的根本運算次數(shù)為的根本運算次數(shù)為 tI，平均情況下的時間復，平均情況下的時間復雜度為雜度為 SIIIptnA)( ninpnpnpnpinA1)1(2)1()1()( 最好、最壞和平均時間復雜度最好時間復雜度最壞時間復雜度平均時間復雜度T(n,I) DT(n,I)|IminB(n)n ) T(n,IDT(n,I)|ImaxW(n)*n nDI P(I)T(n,I)A(n)1.3.3 使用程序步分析算法 一個程序步program step是指在語法上或語義上有意義的程序段，

9、該程序段的執(zhí)行時間必須與問題實例的規(guī)模無關(guān)?！境绦?-1】 求數(shù)組元素累加之和的迭代程序float Sum(float list, const int n) float tempsum=0.0; count +; /針對賦值語句 for (int i=0; in; i+ ) count +; /針對for循環(huán)語句 tempsum+ =listi; count +; /針對賦值語句 count +; /針對for的最后一次執(zhí)行 count +; /針對return語句 return tempsum;求數(shù)組元素累加之和的遞歸程序float RSum (float list, const int n

10、) count +; /針對 if 條件 if (n) count+; /針對 RSum 調(diào)用和return語句 return RSum(list, n-1)+listn-1; count+; /針對return語句 return 0;設(shè)RSumlist,n的程序步為T(n) n )T(n n T(n)0210 2T(n)=2+T(n-1)=2+2+T(n-2) =2*3+T(n-3) =2*n+T(0) =2*n+21.3.4 算法的空間復雜度 一個算法的空間復雜度space complexity是指算法運行所需的存儲空間。 程序運行所需的存儲空間包括以下兩局部： 固定空間需求fixed s

11、pace requirement 這局部空間與所處理數(shù)據(jù)的大小和個數(shù)無關(guān)，也就是說，與問題實例的特征無關(guān)。 可變空間需求variable space requirement 這局部空間大小與算法在某次執(zhí)行中處理的特定數(shù)據(jù)的規(guī)模有關(guān)。 1.4 漸近表示法 1.4.1 大O記號 定義1-1 設(shè)函數(shù)f(n)和g(n)是定義在非負整數(shù)集合上的正函數(shù)，如果存在兩個正常數(shù)c和n0，使得當nn0時，有f(n)cg(n)，那么記做f(n) = O(g(n)，稱為大O記號big Oh notation。f(n) = 2n + 3 = O(n)當n3時，2n+33n，所以，可選c = 3，n0 = 3。對于nn0

12、，f(n) = 2n + 33n，所以，f(n) = O(n)，即2n + 3O(n)。這意味著，當n3時，程序2-1的程序步不會超過3n，2n + 3 = O(n)。 f(n) = 10n2 + 4n + 2 = O(n2)對于n2時，有10n2 + 4n + 210n2 + 5n，并且當n5時，5nn2，因此，可選c = 11, n0 = 5；對于nn0，f(n) = 10n2 + 4n + 211n2，所以f(n) = O(n2)。 f(n) = n！= O(nn)對于n1，有n(n 1)(n 2) 1nn，因此，可選c = 1，n0 = 1。對于nn0，f(n) = n！nn，所以，f

13、(n) = O(nn)。 10n2 + 9 O(n)使用反證法，假定存在c和n0，使得對于nn0，10n2 + 9cn始終成立，那么有10n + 9/nc，即nc/10 9/(10n)總成立。但此不等式不可能總成立，取n = c/10 + 1時，該不等式便不再成立。 定理1-1 如果f(n) = amnm + am1nm1 + + a1n + a0是m次多項式，且am0，那么f(n) = O(nm)。 證明：取n0 = 1，當nn0時，有 f(n)= amnm + am1nm1 + + a1n + a0 |am|nm + |am1|nm1 + + |a1|n + |a0| (|am| + |a

14、m1|/n + + |a1|/nm1 + |a0|/nm) nm (|am| + |am1| + + |a1| + |a0|) nm 可取c= |am| + |am1| + + |a1| + |a0|，定理得證。 漸近時間復雜度 使用大O記號與下面定義的幾種漸近表示法表示的算法時間復雜度，稱為算法的漸近時間復雜度asymptotic complexity。 只要適中選擇關(guān)鍵操作，算法的漸近時間復雜度可以由關(guān)鍵操作的執(zhí)行次數(shù)之和來計算。一般地，關(guān)鍵操作的執(zhí)行次數(shù)與問題的規(guī)模有關(guān)，是n的函數(shù)。 【程序1-3】 矩陣乘法fori=0; in; i+ /n+1 forj=0; jn; j+ /n(n+

15、1) cij=0; /n2 fork=0; kn; k+ /n2(n+1) cij+=aik*bkj; /n3 1.4.2 記號 定義1-2 設(shè)有函數(shù)f(n)和g(n)是定義在非負整數(shù)集合上的正函數(shù)，如果存在兩個正常數(shù) c和n0，使得當nn0時，有f(n)c g(n)，那么記做f(n) = (g(n)，稱為記號omega notation。 f(n) = 2n + 3 = (n)對所有n，2n+32n，可選c = 2，n0=0。對于nn0，f(n) = 2n+32n，所以，f(n) = (n)，即2n + 3(n)。 f(n) = 10n2 + 4n + 2 = (n2)對所有n，10n2 +

16、 4n + 210n2，可選c = 10，n0 = 0。對于nn0，f(n) = 10n2 + 4n + 210n2，所以，f(n) = (n2)。1.4.3 記號 定義1-3 設(shè)有函數(shù)f(n)和g(n)是定義在非負整數(shù)集合上的正函數(shù)，如果存在正常數(shù)c1，c2和n0，使得當nn0時，有c1 g(n)f(n)c2 g(n)，那么記做f(n) = (g(n)，稱為記號Theta notation。1.4.4 小o記號 定義1-4 f(n) = o(g(n)當且僅當f(n) = O(g(n)且f(n) (g(n) 例2-9 f(n)=2n+3=o(n2)，即2n+3o(n2)。 1.4.5 算法按時

17、間復雜度分類 算法按計算時間分類 凡漸近時間復雜度有多項式時間限界的算法稱做多項式時間算法polynomial time algorithm，而漸近時間復雜度為指數(shù)函數(shù)限界的算法稱做指數(shù)時間算法exponential time algorithm。最常見的多項式時間算法的漸近時間復雜度 O(1)O(log n)O(n)O(nlog n)O(n2)O(n3)最常見的指數(shù)時間算法的漸近時間復雜度 O(2n)O(n！)O(nn)總結(jié)定義定義1.1 設(shè)設(shè) f 和和g是定義域為自然數(shù)集是定義域為自然數(shù)集 N上的函數(shù)上的函數(shù). (1) 假設(shè)存在正數(shù)假設(shè)存在正數(shù) c 和和 n0使得對一切使得對一切 n n0

18、有有0 f(n) cg(n) 成立成立, 那么稱那么稱 f(n) 的漸近的上界是的漸近的上界是 g(n)，記作，記作 f (n) = O(g(n). (2) 假設(shè)存在正數(shù)假設(shè)存在正數(shù) c 和和 n0，使得對一切，使得對一切 n n0有有 0 cg(n) f(n) 成立成立, 那么稱那么稱 f(n)的漸近的下界是的漸近的下界是 g(n)，記作，記作 f (n) = (g(n).(3) 假設(shè)假設(shè) f (n) = O(g(n) 且且 f (n) = (g(n), 那么記作那么記作 f (n)=(g(n).(4) 假設(shè)對任意正數(shù)假設(shè)對任意正數(shù) c 都存在都存在 n0，使得當，使得當 n n0 時有時有

19、 0 f(n) 0, 那么 f(n)=(g(n). (2) 如果 ，那么 f(n)=o(g(n). (3) 如果 ，那么 f(n)=(g(n). 有關(guān)定理 )()(limngnfn 0)()(lim ngnfn )()(limngnfn證證 根據(jù)極限定義，對于給定的正數(shù) =c/2, 存在某個n0，只要 nn0，就有對所有的nn0， f(n)2cg(n). 從而推出 f(n)=O(g(n) 對所有的nn0， f(n)(c/2)g(n)，從而推出 f(n)=(g(n), 于是 f(n)= (g(n)ccngnfccngnfccngnf223)()(2)()(|)()(| 一些性質(zhì) 定理定理1.2

20、設(shè) f, g, h是定義域為自然數(shù)集合的函數(shù)， (1) 如果 f=O(g) 且 g=O(h)，那么 f=O(h).(2) 如果 f=(g) 且 g=(h)，那么 f=(h).(3) 如果 f=(g) 和 g=(h)，那么 f=(h).定理定理1.3 假設(shè)假設(shè) f 和和 g是定義域為自然數(shù)集合的函數(shù)，假設(shè)對是定義域為自然數(shù)集合的函數(shù)，假設(shè)對某個其它的函數(shù)某個其它的函數(shù) h, 有有 f=O(h) 和和 g=O(h)，那么，那么 f + g = O(h). 對數(shù)函數(shù))log(log 0)(log)log(logloglog)(loglogloglogloglog2nnnanonnnnnnnlkanb

21、kkbb 性性質(zhì)質(zhì)：符符號號： 階乘)1(1()e(2!nnnnn n! = o(nn) n! = (2n) log(n!) = (nlogn)Stirling公式公式1lneln2lnlimln)(1)e(2ln(limln) !ln(lim2ln/ln2ln/ ) !ln(limlog) !log(lim nnnnnnnncnnnnnnnnnnnnnnnnn（上述的上述的c為某個常數(shù)為某個常數(shù)例5：函數(shù)的階) !log(,log,2,log,loglog,2,)(log,log,)2/3(,2, !, 1,loglog3loglog2loglog/12nnnnnnnnnnnnnnnnnnn

22、nn按照階從高到低對以下函數(shù)排序：)1(,loglog,log,log,log),2(),log() !log(,)(log,)2/3(,2, !,2log/12log3logloglog2nnnnnnnnnnnnnnnnnnnnn 結(jié)果：取整函數(shù) x ：表示小于等于 x 的最大的整數(shù) x ：表示大于等于 x 的最小的整數(shù)取整函數(shù)具有下述性質(zhì)：(1) x 1 x x x x+1 (2) x+n = x +n, x+n = x +n，其中，其中n為整數(shù)為整數(shù) (3) nnn 22 abnbanabnban,(4) 幾個有用的結(jié)果： 和的上界 假設(shè)存在常數(shù) r 1，使得 對一切 k 0 成立，那么

23、求和 nknnkknnkknnkkOnkxxxqqaaqaana1101011)1(ln111,1)1(2)(max1naankk rararaakkkknkk 1000000raakk 1求和實例例例6 估計估計 的上界的上界. . 解解 由由 得得 nkkk131131,3 kkkkkaka321311 kkaakk 1321131)32(313111 kknkkk1.5 遞推關(guān)系 1.5.1 遞推方程求解方法: 遞歸法 迭代法 遞歸樹的應(yīng)用 設(shè)序列a0, a1, , an, , 簡記為an, 一個把an與某些個ai(in)聯(lián)系起來的等式叫做關(guān)于序列 an 的遞推方程 遞推方程recurr

24、ence equation是自然數(shù)上一個函數(shù)T(n)，它使用一個或多個小于n時的值的等式或不等式來描述。遞推方程也稱為遞推關(guān)系或遞推式。 遞推方程必須有一個初始條件稱邊界條件。 例7：Hanoi塔 漢諾塔問題tower of Hanoi 假定有三個塔座：X，Y，Z，在塔座X上有n個直徑大小各不一樣，按圓盤大小從小到大編號為1，2，n的圓盤?，F(xiàn)要求將X塔座上n個圓盤移到塔座Y上，并仍按同樣順序疊排。 圓盤移動時必須遵循以下規(guī)那么：1每次只能移動一個圓盤；2圓盤可以加到塔座X，Y，Z中任意一個上；3任何時刻都不能將一個較大的圓盤放在較小的圓盤之上。算法1.3 Hanoi(A,C,n) / 將A的n

25、個盤子按要求移到C1. if n=1 then move (A,C) / 將A的1個盤子移到C2. else Hanoi(A,B,n1) 3. move(A,C)4. Hanoi(B,C,n1) T(n) = 2 T(n1) + 1，T(1) = 1， A B C迭代解得 T(n) = 2n 1 1 1秒移秒移1 1個，個，64個盤子要多少時間？個盤子要多少時間？( (5000億年億年) ) 漢諾塔問題enum tower A=X, B=Y, C=Z;void Move(int n,tower x,tower y) /將第n個圓盤從塔座x移到塔座y的頂部cout The disk n is m

26、oved from char(x) to top of tower char(y) 0 and x1為常數(shù)，f(n)為函數(shù)，T(n)為非負整數(shù)，且 T(n)=aT(n/b)+f(n) 那么有以下結(jié)果：, 0),()(. 3)log()(),()(. 2)()(, 0),()(1.logloglogloglog aaaaabbbbbnnfnnnTnnfnnTnOnf若若那那么么若若那那么么若若 且對某個常數(shù) c 1和所有充分大的 n 有 a f(n/b) c f(n)，那么 T(n)= (f(n)主定理的證明110log11011222)1()()()1()()(.)()(.)()()()()()()()()(cTbnfancbnfaTanfbnafbnfabnTanfbnafbnTanfbnfbnaTanfbnaTnTkjjjakjjjkkkkkb 不妨設(shè)不妨設(shè)n=bk 情況1)()(log abnOnf)()(10lo