算法優(yōu)化策略ppt課件-展示頁
2025-05-08 02:45本頁面
【正文】 當(dāng)前行，不必存儲(chǔ)整個(gè)數(shù)組。b(i， 0)=0， (1? i ?m)。 設(shè) b(i， j)表示數(shù)組 a的前 j項(xiàng)中 i個(gè)子段和的最大值，且第 i個(gè)子段含 a[j](1? i ?m， i? j ?n)。 ? ?? ??2121]][[)2,1,2,1(iiijjjjiajjiis)2,1,2,1(m a x211 211jjiisnjj mii ??? ???)2,1(m a x)}2,1,2,1(m a x{m a x)2,1,2,1(m a x 211211211211 211iitjjiisjjiis miinjjmiinjj mii ???????????? ?????? ?? ??????? ?? 2 1 2 1211211 ]][[m a x)2,1,2,1(m a x)2,1( j jj i iinjjnjj jiajjiisiit??? 21 ]][[][ i ii jiajb ?????? 2 1211 ][m a x)2,1( j jjnjj jbiit由于解最大子段和問題的動(dòng)態(tài)規(guī)劃算法需要時(shí)間 O(n)，故算法的雙重 for循環(huán)需要計(jì)算時(shí)間 O(m2n)。 } return sum。 else b=a[i]。i=n。 int sum=0, b=0。由此可得計(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)空間。據(jù)此可設(shè)計(jì)出求最大子段和的分治算法。因此，可以在 a[1:n/2]中計(jì)算出 ，并在a[n/2+1:n]中計(jì)算出 。 對(duì)于情形 (3)。 ?? ??? ?? 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種情況。 } thissum+=a[j]。 bestj=j。 if (thissumsum) { sum=thissum。k=j。j=n。i++) { int thissum=0。 for (int i=1。依此定義，所求的最優(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=。1 第 10章 算法優(yōu)化策略 2 算法設(shè)計(jì)策略的比較與選擇 3 最大子段和問題 給定由 n個(gè)整數(shù) (可能為負(fù)整數(shù) )組成的序列 a1,a2,…,a n,求該序列形如 的子段和的最大值。當(dāng)所有整數(shù)均為負(fù)整數(shù)時(shí)定義其最大子段和為０。 int sum=0。i=n。 for (int j=i。j++) { for (int k=i。k++) thissum+=a[k]。 besti=i。 } } return sum。 注意到 ，則可將算法中的最后一個(gè) for循環(huán)省去，避免重復(fù)計(jì)算只需要 O(n2)的計(jì)算時(shí)間。 (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。容易看出， a[n/2]與 a[n/2+1]在最優(yōu)子序列中。則 s1＋ s2即為出現(xiàn)情形 (3)時(shí)的最優(yōu)值。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1