北郵算法設(shè)計(jì)與 第一章 引言

1、引言 參考書： D.E Knuth The Art of Computer Programming, Vol1.Fundamental Algorithms, Vol2.Seminumerical Algorithms Vol3.Search and Sorting Aho,Hopcroft,Ullman,The Design and Analysis of Computer Algorithms, Addison-Wesley,1974 Horwitz,Sahni,Rajasekaran,Computer Algorithms C+ Corman T H, Leiserson C E, Ri

2、vest,R L, Stein C. Introduction to Algorithms ,Second Edition,The MIT Press 王曉東，算法設(shè)計(jì)與分析，清華大學(xué)出版社，2003.1內(nèi)容 數(shù)學(xué)工具線性遞歸關(guān)系，母函數(shù) 數(shù)論算法質(zhì)數(shù)判定，整數(shù)的分解 分類和查找 設(shè)計(jì)方法分治法、貪婪法、動(dòng)態(tài)規(guī)劃、搜索算法 隨機(jī)算法隨機(jī)數(shù)生成、離散和連續(xù)的分布抽樣 ，Monte Carlo法，優(yōu)化中應(yīng)用引言三個(gè)例子快速分類Strassen矩陣乘法 一個(gè)計(jì)算的方法 例1.快速分類 示例:對(duì)3,9,1,6,5,4,8,2,10,7進(jìn)行從小到大的排序快速分類過(guò)程：劃分(續(xù))3 9 1 6 5 4 8

3、 2 10 7i j k=33 9 1 6 5 4 8 2 10 7 SWAP! i j2 9 1 6 5 4 8 3 10 7i j 2 9 1 6 5 4 8 3 10 7 i j SWAP! 2 3 1 6 5 4 8 9 10 7 i j2 3 1 6 5 4 8 9 10 7 i j 2 1 3 | 6 5 4 8 9 10 7 ij快速分類過(guò)程描述原始列3 9 1 6 5 4 8 2 10 7第一輪排序后2 1 | 3 | 6 5 4 8 9 10 7表示成樹(shù)的形式:2，16 5 4 8 9 10 733 9 1 6 5 4 8 2 10 7快速分類過(guò)程特點(diǎn)與性質(zhì) 分治法 遞歸進(jìn)行

4、 以主元進(jìn)行劃分：Partition() 再對(duì)小于和大于主元的兩個(gè)部分進(jìn)行遞歸調(diào)用 對(duì)于樹(shù)形表示,比較總數(shù)等于各點(diǎn)到根距離的總和 實(shí)例中排序完成的樹(shù)321468571093 9 1 6 5 4 8 2 10 7快速分類復(fù)雜度分析 最壞情況 線序：每個(gè)內(nèi)點(diǎn)僅一個(gè)兒子) 1(21) 1() 2(210nnnn)(2NO復(fù)雜度：快速分類復(fù)雜度分析 最好情況使樹(shù)盡可能矮,即樹(shù)均衡;當(dāng)每個(gè)內(nèi)點(diǎn)有兩個(gè)兒子時(shí),有下面關(guān)系2*葉子到根的距離之和= 頂點(diǎn)到根的距離之和+頂點(diǎn)數(shù)-1如:h層完全二叉樹(shù) hkhkhk1122)2(2) 1(頂點(diǎn)到樹(shù)根距離之和12)1(hh葉子到根距離之和12h頂點(diǎn)數(shù)最好情況葉子到根的

5、距離為:故葉子到根距離和約為:頂點(diǎn)到根的距離之和= 2*葉子到根的距離之和-頂點(diǎn)數(shù)+1nn22loglog或nn2log12log) 1(2log) 1(log2222NNNNNNNnn)log(NNO若葉子數(shù)目為n，則內(nèi)點(diǎn)為n-1，頂點(diǎn)數(shù)目為N=2n-1;即最好情下復(fù)雜度比較次數(shù)約為快速分類復(fù)雜度分析:平均情況 較的平均比較次數(shù)個(gè)對(duì)象進(jìn)行分類所作比對(duì)nTn若取第k個(gè)數(shù)為分割標(biāo)準(zhǔn)，則一個(gè)序列有(k-1)個(gè)數(shù)，另一個(gè)有(n-k)個(gè)數(shù)，從而分割標(biāo)準(zhǔn)：可任意選取平均：如何做？0, 0, 1321)1(10121011TTTnTnnTTnnTnkknkknkn快速分類復(fù)雜度分析:平均情況求解nkknn

6、kknTnnTnTnnnT01102)1()1(2)1(相減nTnTnTnnTTnnnnnn2)2() 1(22) 1(11除以 (n+1)(n+2) 2)(1(2121nnnnTnTnn0, 0, 132101210TTTnTnnTnkkn變換快速分類復(fù)雜度分析:平均情況 代入得) 1/( nTSnn變換 0)2)(1(201SnnnSSnn101010221412112214)2)(1(2nknknknknnkkkkkkS估計(jì)和：用求和進(jìn)行逼近，與分析中的黎曼和處理相同，只需上界0,31)2)(1(20121SSSnnnSSnn快速分類復(fù)雜度分析:平均情況)1(ln2212)ln(2Onn

7、nSn)(ln) 1( 2nOnnTn)log(NNOTNnxdxxknnnklnln11112)(log3863. 12nOnnTn時(shí)間復(fù)雜度 例2.Strassen矩陣乘法 給定兩個(gè)的矩陣A和B，求它們的積 C = A B 算法:kkjikijbac直接相乘做累加，需要做N3 乘法,為O(N3) Strassen矩陣乘法計(jì)算222112112221121122211211BBBBAAAACCCC) )( - ( ) )( -( ) ( ) -( )- ( ) ( ) ( ) ( 2221221212 1111 2122121111 212222121111222122 112211BBAA

8、V BBAAUBAATBBAS BBARBAAQ BBAAP U R - Q P C S Q C TR C V S - T P C 22 21 1211Strassen矩陣乘法分析 高階的1個(gè)乘法化成為低階的7個(gè)乘法解該關(guān)系得T(n) = O(nlog 7) = O(n2.81). 顯然比直接做乘法會(huì)減少！代價(jià)：使用空間增加，加法量也增加！Hopcroft 和Kerr 在1971 年已經(jīng)證明：計(jì)算22 矩陣的乘積，7 次乘法是必要的! 最好的上界為 n2.376 11)2(7)(nifcnifcnnTnT例3 .一個(gè)計(jì)算的方法 假定能夠均勻地扔到一個(gè)正方形中，計(jì)算落入其中的點(diǎn)個(gè)數(shù)。通過(guò)計(jì)數(shù)其中

9、落入內(nèi)切圓的點(diǎn)的個(gè)數(shù)；如果一共投入N個(gè)點(diǎn)，其中有M個(gè)落入圓中，則只要點(diǎn)均勻，假定圓周的半徑為R，則,即22)2( RRNMNM 4該方法得到的要得到的精度與投入點(diǎn)的個(gè)數(shù)有關(guān)，一般個(gè)數(shù)較大時(shí)精度比較高。隨機(jī)計(jì)算隨機(jī)計(jì)算的程序的程序 double rand_pi(int n)int numInCircle=0;double x,y;double pi;for(int i=0;in;i+)x=rand()/(double)RAND_MAX;y=rand()/(double)RAND_MAX;if(x*x+y*y1) numInCircle+;pi=(4.0*numInCircle)/n;return pi;一個(gè)運(yùn)行結(jié)果：次數(shù)10102103104105106107108109估值3.63.083.0843.11323.139683.1399243.14097523.141385083.141537232畫分網(wǎng)格計(jì)算畫分網(wǎng)格計(jì)算的程序的程序 double grid_pi(int n)int i;double sum=0;for(i=0;in;i+)sum+=(int)sqrt(n*(double)n-i*(double)i);retur