【正文】 ③算法是否易讀、易移植等等其它問題 影響時(shí)間特性的四個(gè)因素 ： ①程序運(yùn)行時(shí)輸入數(shù)據(jù)的總量 ②對(duì)源程序編譯所需的時(shí)間 ③計(jì)算機(jī)執(zhí)行每條指令所需的時(shí)間 ④程序中指令重復(fù)執(zhí)行的次數(shù) * [定義 ] 語句頻度 ：語句重復(fù)執(zhí)行的次數(shù) ?程序運(yùn)行時(shí)間 . 算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 7 第二章 算法設(shè)計(jì)與分析的基本方法與技巧 國家示范性軟件學(xué)院 2020 g(n) ) . 算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 8 第二章 算法設(shè)計(jì)與分析的基本方法與技巧 國家示范性軟件學(xué)院 2020 秋 (2) 語句序列 T(s1,s2,…,s k)=max{T(s1),T(s2),…,T(s k)) (3) 條件語句 T( if (B) s1 else s2)=T(B)+T(else)+max{T(s1),T(s2)} 通常取 T(B)+T(else)=O(1) T(if(B) s )=O(1)+T(s) (4) Switch語句 設(shè)語句 s switch(E) { case E1: S1。i=n。 秋 (7) 函數(shù)調(diào)用 遞歸調(diào)用： ∑被調(diào)用子函數(shù)運(yùn)行時(shí)間 非遞歸調(diào)用：求解遞歸方程 (8) goto語句 goto語句破壞了程序結(jié)構(gòu) 一般對(duì) goto語句限制使用 對(duì)有條件的 goto轉(zhuǎn)移可忽略不計(jì) . 算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 14 第二章 算法設(shè)計(jì)與分析的基本方法與技巧 國家示范性軟件學(xué)院 2020 in1。 O(1) O(1) =(ni1) =O(n2) A[j1]=A[j]。 → f(n) = 1。 s += x。 ++i ) for( j=1 。 } → f(n) = 3n2+2n+1。 j =n 。 ++k ) c[i][j] += a[i][k] * b[k][j] 。 else return( n * fact( n – 1 ) )。 else { m=(i+j1)/2。 若推理過程能夠完成且待定參數(shù)能夠確定，則求解完畢。 . 算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 19 第二章 算法設(shè)計(jì)與分析的基本方法與技巧 國家示范性軟件學(xué)院 2020 . 算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 20 第二章 算法設(shè)計(jì)與分析的基本方法與技巧 國家示范性軟件學(xué)院 2020 T(n/c)是求解一個(gè)子問題的時(shí)間開銷。 秋 T(n)=ai T(n/ci)+∑ajd(n/cj) i1 j=0 假設(shè) n=ck，則 T(n/ck)=T(1)=1, 令 i=k 有： T(n)= ak+∑ajd(ckj) 利用 k=log，則上式第一項(xiàng)可寫成 alogc 或等價(jià)于 nlogc k1 j=0 n a 齊次解與特解： 當(dāng) d(n)=0時(shí)， ak或 alogc 稱為方程的齊次解。 秋 定理： 設(shè) a,c是非負(fù)常數(shù)， n是 2的冪， d(n)是倍積函數(shù)，則 T(n) = b n=1 aT(n/c)+d(n) n1 的齊次解是 O(nlogc )，且對(duì)特解有如下結(jié)論： (1)若 ad(c)，則特解是 O(ak)，或 O(nlogc ),即特解與齊次解同階 (2)若 ad(c)，則特解是 O((d(c)k)，或 O(nlogcd(c))即特解與 d同階 (3)若 a=d(c)，則特解是齊次解的 log。遞 歸地解這些子問題，然后將各子問題的解合并得到原 問題的解。 else { (m1,…,m k)=divide(p,q)。 小問題通常與原問題相似，可以遞歸使用分治策略來解決。y的積可寫成： x2n/2+d) =ac) cd)] else { s=sign(x)*sign(y)。 u=mult(ab,dc,n/2)。y 31 41 53 27 x= y= x=3141 a=31 b=41 ab=10 y=5327 c=53 d=27 dc=26 ay=a(dc)+b104+[(1643)*+(260)*+(1107)*] (d1c1)=4 ad2=7, (a2b2) c3=2, b3102+(2+0+4) 上是可變換成： 4/a 秋 引理 兩個(gè) 2 2矩陣 (元素來自任意的環(huán) )之積可以用 7次相乘和 18次相加 (減 )完成。 例如：常見的是“冒泡”分類算法就是一個(gè)不平衡的例子。先對(duì)每個(gè)子序列進(jìn)行分類，然后 對(duì)已分類的子序列進(jìn)行歸并（最多需要 n1次比較），合并成一 個(gè)有序序列。 滿足約束條件的任意子集叫做可用解，使給定的目標(biāo)值達(dá)到 最大（或最?。┑目捎媒饨凶鲎罴呀狻?{ solution = ￠； for( i = 1。 } return solution 。 秋 在貪心算法（ greedy method）中采用逐步構(gòu)造最優(yōu)解的方法。 [例找零錢 ] 一個(gè)小孩買了價(jià)值少于 1美元的糖，并將 1美元的錢交給售貨員。選擇硬幣時(shí)所采用的貪婪準(zhǔn)則如下：每一次選擇應(yīng)使零錢數(shù)盡量增大。對(duì)象的重量為 wi。目標(biāo) :在 n個(gè)對(duì)象中選 取若干對(duì)象，將背包裝滿 (所選對(duì)象的總重量不超過 M),使總增 益最大。即按先輕后重 的順序來選擇對(duì)象。 秋 x1,x2,x3 ∑wixi ∑pixi 1 (1/2,1/3,1/4) 2 (1,2/15,0) 20 3 (0,2/3,1) 20 31 4 (0,1,1/2) 20 例：設(shè) n=3,M=20,(p1,p2,p3)=(25,24,15),(w1,w2,w3)=(18,15,10) 按策略 1，對(duì)象 1的增益率 p1最大，取 x1=1, 則背包容量尚余 Mw1=2。 Void KnapSack (LIST w 。 int n ) { int i , cu 。 cu = M 。 x[i] = 1 。 秋 定理 若 p1/w1≥p2/w2≥…≥p n/wn 則算法 Knapsack對(duì)給定的 背包問題生成全局最佳解。 如果存在一種符合上 述要求的選擇，則稱此背包問題有解 (或稱其解為真 )；否則稱此 背包問題無解 (或稱其解為假 )。 if ( s 0 || s 0 amp。 return True。 ?起源于二十世紀(jì)五十年代（貝爾曼 ） ?屬于現(xiàn)代控制理論的一部分 ?以長遠(yuǎn)利益為目標(biāo)的一系列決策 ?最優(yōu)化原理，可歸結(jié)為一個(gè)遞推公式 ?又稱為對(duì)階段規(guī)劃，特點(diǎn)體現(xiàn)在多階段性 ?動(dòng)態(tài)規(guī)劃 . 算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 39 第二章 算法設(shè)計(jì)與分析的基本方法與技巧 國家示范性軟件學(xué)院 2020 貪心法與動(dòng)態(tài)規(guī)劃方法之間的本質(zhì)區(qū)別： 貪心法只生成一個(gè)判定序列，而動(dòng)態(tài)規(guī)劃方法則可能產(chǎn)生許多 判定序列。不然，y1,y2,…,y n就不是 Knap(1,n,M)的最佳序列。 秋 gj(y)=∑pixi ， ∑wixi≤ y ， xi=0/1 (j+1≤i≤n) j+1≤i≤n j+1≤i≤n ?若選 x1=0： g0(M)=∑pixi=∑pixi=g1(M)，約束條件： ∑wixi=∑wixi≤M ?若選 x1=1： g0(M)=∑pixi=p1+∑pixi=p1+g1(Mw1) 關(guān)于目標(biāo)函數(shù)的遞推式： 設(shè) gj(y)是 0/1背包 (子 )問題 Knap(j+1,n,y)的最佳解的目標(biāo)函數(shù)，即： 則 g0(M)是 knap(1,n,M)的最佳解。 1≤i≤n 1≤i≤n 1≤i≤j 1≤i≤j 2≤i≤n 2≤i≤n 2≤i≤n 2≤i≤n 2≤i≤n 2≤i≤n . 算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 42 第二章 算法設(shè)計(jì)與分析的基本方法與技巧 國家示范性軟件學(xué)院 2020 秋 mij = 0 i=j min(mik+mk+1,j+ri1rkrj ij i≤k≤j M = M1 M2 M3 M4 [10 20] [20 50] [50 1] [1 100] M = M1 M2 … Mn M1 (M2 M3 M4) 23000次乘法 (M1 (M2 M3)) M4) 2200次乘法 設(shè) mij是計(jì)算 Mi Mi+1 … Mj的最小代價(jià) 求 n個(gè)矩陣的乘積 . 算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 44 第二章 算法設(shè)計(jì)與分析的基本方法與技巧 國家示范性軟件學(xué)院 2020 for ( l=1 。 i++ ) { j = i+1 。k=