【正文】 結(jié)果； ④ 對(duì)于一切合法的輸入均得到滿(mǎn)足要求的結(jié)果； 算法描述 ： ① 自然語(yǔ)言； ② 程序設(shè)計(jì)語(yǔ)言； ③ 類(lèi)語(yǔ)言 *； 關(guān)于本書(shū)采用的類(lèi)語(yǔ)言描述 ： ① 結(jié)構(gòu)類(lèi)型說(shuō)明 ② 輸入輸出約定 ( cin v , cout v ) ③ new 和 delete ④ 引入引用類(lèi)型 ⑤ 其他 . 算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 6 第二章 算法設(shè)計(jì)與分析的基本方法與技巧 國(guó)家示范性軟件學(xué)院 2020 秋 (1) 表達(dá)式和賦值語(yǔ)句 exp::=常數(shù) | 變量 | Fname(e1,e2,…,e m) | (exp θ exp) T(v=exp)=T(.v)+T(=)+T(exp) T(exp θ exp)=T(exp)+T(θ)+T(exp) T(Fname(e1,e2,…,e m))=T(call/return)+mT(par)+T(Fbody) 例： T(c=a+b)=T(.c)+T(=)+T(a)+T(+)+T(b) 相應(yīng)的匯編程序?yàn)椋? load a in R1 load b in R2 add R2 to R1 load .c in R2 store R1 in R2 ～ ～ 通常取 O(1) . 算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 11 第二章 算法設(shè)計(jì)與分析的基本方法與技巧 國(guó)家示范性軟件學(xué)院 2020 i++} 設(shè) RT0表示某一次循環(huán)開(kāi)始執(zhí)行時(shí)的絕對(duì)時(shí)間 關(guān)于循環(huán)的定時(shí)不變式 RT為 RT=RT0+(i+1)(T(B)+T(while)+i(T(s)+T(j)) 其中： T(while)代表測(cè)試循環(huán)終止條件所耗時(shí)間 T(j)代表跳回循環(huán)頭所耗時(shí)間 可簡(jiǎn)化成： T(j)=T(while) T(while(B)s)=RTRT0=(i+1)T(B)+iT(s)+(2i+1)T(while) . 算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 13 第二章 算法設(shè)計(jì)與分析的基本方法與技巧 國(guó)家示范性軟件學(xué)院 2020 j) O(∑(ni1)) if(A[j1]A[j]) { O((ni1) 1) ≤O(n(n1)/2) temp=A[j1]。 ++i ) { ++x。 s += x。 k = n。 { if(i==j) return(x[i])。 此猜測(cè)失敗。全部數(shù)據(jù)被分割成 c等分，每分的 數(shù)量為 n/c。則有： d(ck1)=(d(c))k1 ∑ajd(ck1)=∑aj(d(c))k1 =(d(c))k∑(a/d(c))j =(ak(d(c))k)/(a/d(c)1) k1 j=0 k1 j=0 k1 j=0 . 算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 23 第二章 算法設(shè)計(jì)與分析的基本方法與技巧 國(guó)家示范性軟件學(xué)院 2020 int dac(int p, int q) { if(small(p,q)) return(G(p,q))。 設(shè) x和 y都是 n位數(shù)， n是 2的冪，將 x和 y各分成兩半，每一半都 是 n/2位數(shù)，則 xd+b(dc) +b a=x的左 n/2位； b=x的右 n/2位； c=y的左 n/2位； d=y的右 n/2位； v=mult(a,c,n/2)。(dc)=(260)* xd =(1643)*c2=8, b2(dc)=2U(n/2)+n2 其中 d(n)=n2是倍積函數(shù)，只要 ma就有 4m/ad(c)， T(n)=O(nlogm) m=8,a=4， T(n)=O(n3) . 算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 29 第二章 算法設(shè)計(jì)與分析的基本方法與技巧 國(guó)家示范性軟件學(xué)院 2020 將 a1,a2,…,an 分成兩個(gè)子序列： a1,a2,…,an/2 和 a(n/2)+1,…,an 。 int n 。 ?貪心法 . 算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 32 第二章 算法設(shè)計(jì)與分析的基本方法與技巧 國(guó)家示范性軟件學(xué)院 2020 售貨員分步驟組成要找的零錢(qián)數(shù)，每次加入一個(gè)硬幣。xi表示重物 wi的幾分之幾 )放入背包， 則得增益 pixi，其中 pi叫做重物 wi的增益率。 . 算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 35 第二章 算法設(shè)計(jì)與分析的基本方法與技巧 國(guó)家示范性軟件學(xué)院 2020 x 。 i++ ) { if ( w[i] cu ) goto L。問(wèn)能否從這 n件物品中選擇若干件放入 此背包中，使得放入的重量之和正好為 S。 if ( Kanp ( s – W[n], n1 ) == True ) { cout W[n] ‘ , ’。 最佳原理 一個(gè)最佳判定序列有這樣一個(gè)性質(zhì)：無(wú)論該序列是從什么初始 狀態(tài)開(kāi)始首次判斷的，其后續(xù)的判斷隊(duì)首次判斷所產(chǎn)生的狀態(tài) 而言，必構(gòu)成最佳判定序列。 . 算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 41 第二章 算法設(shè)計(jì)與分析的基本方法與技巧 國(guó)家示范性軟件學(xué)院 2020 . 算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 43 第二章 算法設(shè)計(jì)與分析的基本方法與技巧 國(guó)家示范性軟件學(xué)院 2020 i = n1 。 秋 ?回溯 。 mi,j=min(Mi,k+Mk+1,j+ri1*rk*rj ) 。 秋 m11=0 m22=0 m33=0 m44=0 m12=10000 m23=1000 m34=5000 m13=1200 m24=3000 m14=2200 { for ( i=1 。 對(duì) x1的可能判定是 0/1： 其中 ∑wixi≤M是對(duì) Knap(2,n,M)的約束條件。 . 算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 40 第二章 算法設(shè)計(jì)與分析的基本方法與技巧 國(guó)家示范性軟件學(xué)院 2020 } return Kanp( s, n1 )。試用遞歸方法設(shè)計(jì)求解背包問(wèn)題 的算法。 cu = cu – w[i] 。 for ( i = 1 。對(duì)象 2的增益率次 之 ,但 w2=15,不能全部裝入 ,故令 x2=2/15,得解 2。 max(∑pixi) 1≤i≤n 約束條件： ∑wixi≤M 0≤xi≤1, pi0, wi0, 1≤i≤n 滿(mǎn)足 的任意集合 {x1,x2,…,xn} 就是可用解 使 最大的可用解即最佳解 1≤i≤n . 算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 34 第二章 算法設(shè)計(jì)與分析的基本方法與技巧 國(guó)家示范性軟件學(xué)院 2020 為保證解法的可行性（即：所給的零錢(qián)等于要找的零錢(qián)數(shù)），所選擇的硬幣不應(yīng)使零錢(qián)總數(shù)超過(guò)最終所需的數(shù)目。在每個(gè)階段，都作出一個(gè)看上去最優(yōu)的決策（在一定的標(biāo)準(zhǔn)下）。 i = n。 T(n) = 0 n=1 2T(n/2)+n1 n1 T(n)=O(nlogn) ?平衡 . 算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 31 第二章 算法設(shè)計(jì)與分析的基本方法與技巧 國(guó)家示范性軟件學(xué)院 2020 M1=(A11－ A12)(B21+B22) M2=(A11+A22)(B11+B22) M3=(A11－ A21)(b11+B12) M4=(A11+A12)B22 M5=A11(B12B22) M6=A22(B21－ B11) M7=(A21+A22)B11 C11=M1+M2M4+M6 C12=M4+M5 C21=M6+M7 C22=M2－ M3+M5－ M7 定理 兩個(gè) n n的矩陣 (元素來(lái)自任意的環(huán) )之積可用 O(nlog7)次 運(yùn)算完成 證：設(shè) n=2k， T(n)是計(jì)算兩個(gè) n n矩陣之積，由引理 T(n)=7T(n/2)+18(n/2)2， n=2 故有： T(n)=O(nlog7) . 算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 30 第二章 算法