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

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

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

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

4、歸并排序：最壞和平均狀況下都為堆排序、二分歸并排序：最壞和平均狀況下都為O(nlogn) 問題問題那個(gè)排序算法效率最高？那個(gè)排序算法效率最高？是否可以找到更好的算法？排序問題的計(jì)算難度如何是否可以找到更好的算法？排序問題的計(jì)算難度如何估計(jì)？估計(jì)？貨郎問題：貨郎問題： 有窮個(gè)城市的集合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 實(shí)例：改進(jìn)的順序檢索 算法1.2 Search(L,x)輸入：數(shù)組L1.n，其元素按照從小到大排列，數(shù) x. 輸出：假設(shè) x 在L中，輸

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

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

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

8、x 在在 L 不同位置不同位置等概分布等概分布. 實(shí)例集實(shí)例集 S，實(shí)例，實(shí)例IS的概率是的概率是 pI, 算法算法對(duì)對(duì)I 的根本運(yùn)算次數(shù)為的根本運(yùn)算次數(shù)為 tI，平均情況下的時(shí)間復(fù)，平均情況下的時(shí)間復(fù)雜度為雜度為 SIIIptnA)( ninpnpnpnpinA1)1(2)1()1()( 最好、最壞和平均時(shí)間復(fù)雜度最好時(shí)間復(fù)雜度最壞時(shí)間復(fù)雜度平均時(shí)間復(fù)雜度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 使用程序步分析算法 一個(gè)程序步program step是指在語法上或語義上有意義的程序段，

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

10、) count +; /針對(duì) if 條件 if (n) count+; /針對(duì) RSum 調(diào)用和return語句 return RSum(list, n-1)+listn-1; count+; /針對(duì)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 算法的空間復(fù)雜度 一個(gè)算法的空間復(fù)雜度space complexity是指算法運(yùn)行所需的存儲(chǔ)空間。 程序運(yùn)行所需的存儲(chǔ)空間包括以下兩局部： 固定空間需求fixed s

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

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

13、(n) = O(nn)。 10n2 + 9 O(n)使用反證法，假定存在c和n0，使得對(duì)于nn0，10n2 + 9cn始終成立，那么有10n + 9/nc，即nc/10 9/(10n)總成立。但此不等式不可能總成立，取n = c/10 + 1時(shí)，該不等式便不再成立。 定理1-1 如果f(n) = amnm + am1nm1 + + 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| + |a

14、m1|/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ù)雜度asymptotic complexity。 只要適中選擇關(guān)鍵操作，算法的漸近時(shí)間復(fù)雜度可以由關(guān)鍵操作的執(zhí)行次數(shù)之和來計(jì)算。一般地，關(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 記號(hào) 定義1-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(n)，稱為記號(hào)omega notation。 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)。 f(n) = 10n2 + 4n + 2 = (n2)對(duì)所有n，10n2 +

16、 4n + 210n2，可選c = 10，n0 = 0。對(duì)于nn0，f(n) = 10n2 + 4n + 210n2，所以，f(n) = (n2)。1.4.3 記號(hào) 定義1-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。1.4.4 小o記號(hào) 定義1-4 f(n) = o(g(n)當(dāng)且僅當(dāng)f(n) = O(g(n)且f(n) (g(n) 例2-9 f(n)=2n+3=o(n2)，即2n+3o(n2)。 1.4.5 算法按時(shí)

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

18、有有0 f(n) cg(n) 成立成立, 那么稱那么稱 f(n) 的漸近的上界是的漸近的上界是 g(n)，記作，記作 f (n) = O(g(n). (2) 假設(shè)存在正數(shù)假設(shè)存在正數(shù) c 和和 n0，使得對(duì)一切，使得對(duì)一切 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è)對(duì)任意正數(shù)假設(shè)對(duì)任意正數(shù) c 都存在都存在 n0，使得當(dāng)，使得當(dāng) n n0 時(shí)有時(shí)有

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ù)極限定義，對(duì)于給定的正數(shù) =c/2, 存在某個(gè)n0，只要 nn0，就有對(duì)所有的nn0， f(n)2cg(n). 從而推出 f(n)=O(g(n) 對(duì)所有的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是定義域?yàn)樽匀粩?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是定義域?yàn)樽匀粩?shù)集合的函數(shù)，假設(shè)對(duì)是定義域?yàn)樽匀粩?shù)集合的函數(shù)，假設(shè)對(duì)某個(gè)其它的函數(shù)某個(gè)其它的函數(shù) h, 有有 f=O(h) 和和 g=O(h)，那么，那么 f + g = O(h). 對(duì)數(shù)函數(shù))log(log 0)(log)log(logloglog)(loglogloglogloglog2nnnanonnnnnnnlkanb

21、kkbb 性性質(zhì)質(zhì)：符符號(hào)號(hào)： 階乘)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為某個(gè)常數(shù)為某個(gè)常數(shù)例5：函數(shù)的階) !log(,log,2,log,loglog,2,)(log,log,)2/3(,2, !, 1,loglog3loglog2loglog/12nnnnnnnnnnnnnnnnnnn

22、nn按照階從高到低對(duì)以下函數(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) 幾個(gè)有用的結(jié)果： 和的上界 假設(shè)存在常數(shù) r 1，使得 對(duì)一切 k 0 成立，那么

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

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

25、個(gè)盤子按要求移到C1. if n=1 then move (A,C) / 將A的1個(gè)盤子移到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個(gè)，個(gè)，64個(gè)盤子要多少時(shí)間？個(gè)盤子要多少時(shí)間？( (5000億年億年) ) 漢諾塔問題enum tower A=X, B=Y, C=Z;void Move(int n,tower x,tower y) /將第n個(gè)圓盤從塔座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)為非負(fù)整數(shù)，且 T(n)=aT(n/b)+f(n) 那么有以下結(jié)果：, 0),()(. 3)log()(),()(. 2)()(, 0),()(1.logloglogloglog aaaaabbbbbnnfnnnTnnfnnTnOnf若若那那么么若若那那么么若若 且對(duì)某個(gè)常數(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