算法優(yōu)化策略ppt課件(已修改)
2025-05-11 02:45 本頁(yè)面
【正文】 1 第 10章 算法優(yōu)化策略 2 算法設(shè)計(jì)策略的比較與選擇 3 最大子段和問(wèn)題 給定由 n個(gè)整數(shù) (可能為負(fù)整數(shù) )組成的序列 a1,a2,…,a n,求該序列形如 的子段和的最大值。當(dāng)所有整數(shù)均為負(fù)整數(shù)時(shí)定義其最大子段和為０。依此定義，所求的最優(yōu)值為 : 例如 : A=(2， 11， 4， 13， 5， 2) 最大子段和為 ??jikka?????? ?????jikknji a1 m ax,0m ax2042???kka4 簡(jiǎn)單算法 public static int maxSum() { int n=。 int sum=0。 for (int i=1。i=n。i++) { int thissum=0。 for (int j=i。j=n。j++) { for (int k=i。k=j。k++) thissum+=a[k]。 if (thissumsum) { sum=thissum。 besti=i。 bestj=j。 } } return sum。 } thissum+=a[j]。 注意到 ，則可將算法中的最后一個(gè) for循環(huán)省去，避免重復(fù)計(jì)算只需要 O(n2)的計(jì)算時(shí)間。 ?? ??? ?? 1j ik kj ik jk aaa5 分治算法 如果將所給的序列 a[1:n]分為長(zhǎng)度相等的 2段 a[1:n/2]和a[n/2+1:n]，分別求出這 2段的最大子段和，則 a[1:n]的最大子段和有 3種情況。 (1)a[1:n]的最大子段和與 a[1:n/2]最大子段和相同； (2)a[1:n]的最大子段和與 a[n/2+1:n]最大子段和相同； (3)a[1:n]的最大子段和為 ，且 1≤i≤n/2， n/2+1≤j≤n。 對(duì)于情形 (3)。容易看出， a[n/2]與 a[n/2+1]在最優(yōu)子序列中。因此，可以在 a[1:n/2]中計(jì)算出 ，并在a[n/2+1:n]中計(jì)算出 。則 s1＋ s2即為出現(xiàn)情形 (3)時(shí)的最優(yōu)值。據(jù)此可設(shè)計(jì)出求最大子段和的分治算法。 ??jikka????? 2/2/1 ][m a x1 n ikni kas? ?????? inknin kas 12/12/ ][m ax2復(fù)雜度分析 T(n)=O(nlogn) nOnTOnT??????? )()2/(2)1()(6 動(dòng)態(tài)規(guī)劃算法 記 ， 1? j ?n，則所求的最大子段和為 當(dāng) b[j1]0時(shí) b[j]=b[j1]+a[j]，否則 b[j]=a[j]。由此可得計(jì)算 b[j]的動(dòng)態(tài)規(guī)劃遞歸式 }][{m ax][ 1 ????? jikjikajb][m ax][m axm ax][m ax 1111 jbkaka njjikjinjjiknji ????????????? ??b[j]=max{b[j1]+a[j]， a[j]}， 1? j ?n 算法顯然需要 O(n)計(jì)算時(shí)間和 O(n)空間。 public static int maxSum() { int n=。 int sum=0, b=0。 for (int i=1。i=n。i++) { if (b0) b+=a[i]。 else b=a[i]。 if (bsum)sum=b。 } return sum。 } 7 最大子矩陣和問(wèn)題 記 最大子矩陣和問(wèn)題的最優(yōu)值為 由于 其中， 設(shè) ，則 給定一個(gè) m行 n列的整數(shù)矩陣 a，試求矩陣 a的一個(gè)子矩陣，使其各元素之和為最大。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1