【正文】 ③算法是否易讀、易移植等等其它問題 影響時間特性的四個因素 ： ①程序運行時輸入數(shù)據(jù)的總量 ②對源程序編譯所需的時間 ③計算機執(zhí)行每條指令所需的時間 ④程序中指令重復執(zhí)行的次數(shù) * [定義 ] 語句頻度 ：語句重復執(zhí)行的次數(shù) ?程序運行時間 . 算法與數(shù)據(jù)結構 Slides. 2 7 第二章 算法設計與分析的基本方法與技巧 國家示范性軟件學院 2020 g(n) ) . 算法與數(shù)據(jù)結構 Slides. 2 8 第二章 算法設計與分析的基本方法與技巧 國家示范性軟件學院 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語句 設語句 s switch(E) { case E1: S1。i=n。 秋 (7) 函數(shù)調(diào)用 遞歸調(diào)用： ∑被調(diào)用子函數(shù)運行時間 非遞歸調(diào)用：求解遞歸方程 (8) goto語句 goto語句破壞了程序結構 一般對 goto語句限制使用 對有條件的 goto轉移可忽略不計 . 算法與數(shù)據(jù)結構 Slides. 2 14 第二章 算法設計與分析的基本方法與技巧 國家示范性軟件學院 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ù)結構 Slides. 2 19 第二章 算法設計與分析的基本方法與技巧 國家示范性軟件學院 2020 . 算法與數(shù)據(jù)結構 Slides. 2 20 第二章 算法設計與分析的基本方法與技巧 國家示范性軟件學院 2020 T(n/c)是求解一個子問題的時間開銷。 秋 T(n)=ai T(n/ci)+∑ajd(n/cj) i1 j=0 假設 n=ck，則 T(n/ck)=T(1)=1, 令 i=k 有： T(n)= ak+∑ajd(ckj) 利用 k=log，則上式第一項可寫成 alogc 或等價于 nlogc k1 j=0 n a 齊次解與特解： 當 d(n)=0時， ak或 alogc 稱為方程的齊次解。 秋 定理： 設 a,c是非負常數(shù)， n是 2的冪， d(n)是倍積函數(shù)，則 T(n) = b n=1 aT(n/c)+d(n) n1 的齊次解是 O(nlogc )，且對特解有如下結論： (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 秋 引理 兩個 2 2矩陣 (元素來自任意的環(huán) )之積可以用 7次相乘和 18次相加 (減 )完成。 例如：常見的是“冒泡”分類算法就是一個不平衡的例子。先對每個子序列進行分類，然后 對已分類的子序列進行歸并（最多需要 n1次比較），合并成一 個有序序列。 滿足約束條件的任意子集叫做可用解，使給定的目標值達到 最大（或最?。┑目捎媒饨凶鲎罴呀?。 { solution = ￠； for( i = 1。 } return solution 。 秋 在貪心算法（ greedy method）中采用逐步構造最優(yōu)解的方法。 [例找零錢 ] 一個小孩買了價值少于 1美元的糖，并將 1美元的錢交給售貨員。選擇硬幣時所采用的貪婪準則如下：每一次選擇應使零錢數(shù)盡量增大。對象的重量為 wi。目標 :在 n個對象中選 取若干對象，將背包裝滿 (所選對象的總重量不超過 M),使總增 益最大。即按先輕后重 的順序來選擇對象。 秋 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 例：設 n=3,M=20,(p1,p2,p3)=(25,24,15),(w1,w2,w3)=(18,15,10) 按策略 1，對象 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對給定的 背包問題生成全局最佳解。 如果存在一種符合上 述要求的選擇，則稱此背包問題有解 (或稱其解為真 )；否則稱此 背包問題無解 (或稱其解為假 )。 if ( s 0 || s 0 amp。 return True。 ?起源于二十世紀五十年代（貝爾曼 ） ?屬于現(xiàn)代控制理論的一部分 ?以長遠利益為目標的一系列決策 ?最優(yōu)化原理，可歸結為一個遞推公式 ?又稱為對階段規(guī)劃，特點體現(xiàn)在多階段性 ?動態(tài)規(guī)劃 . 算法與數(shù)據(jù)結構 Slides. 2 39 第二章 算法設計與分析的基本方法與技巧 國家示范性軟件學院 2020 貪心法與動態(tài)規(guī)劃方法之間的本質(zhì)區(qū)別： 貪心法只生成一個判定序列，而動態(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) 關于目標函數(shù)的遞推式： 設 gj(y)是 0/1背包 (子 )問題 Knap(j+1,n,y)的最佳解的目標函數(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ù)結構 Slides. 2 42 第二章 算法設計與分析的基本方法與技巧 國家示范性軟件學院 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次乘法 設 mij是計算 Mi Mi+1 … Mj的最小代價 求 n個矩陣的乘積 . 算法與數(shù)據(jù)結構 Slides. 2 44 第二章 算法設計與分析的基本方法與技巧 國家示范性軟件學院 2020 for ( l=1 。 i++ ) { j = i+1 。k=