算法設(shè)計(jì)與分析第07章-資料下載頁
2025-08-04 10:40本頁面
【正文】 for(int i=0。in。i++) if(a[i]b[i]) { d[i].jobNo=i。d[i].ab=0。d[i].t=a[i]。 } else { d[i].jobNo=i。d[i].ab=1。d[i].t=b[i]。 } Sort(d,n)。 int left=0,right=n1。 for (i=0。in。i++) if(d[i].ab==0) c[left++]=d[i].jobNo。 else c[right]=d[i].jobNo。 } Johnson算法的時(shí)間取決于對(duì)作業(yè)集合的排序，因此，在最壞情況下算法的時(shí)間復(fù)雜度為 O(nlogn)，所需的空間復(fù)雜度為 O(n)。 例題：最大子段和 ? 問題描述： ? 給定由 n個(gè)整數(shù)（包含負(fù)整數(shù)）組成的序列 a1,a2,...,an，求該序列子段和的最大值。當(dāng)所有整數(shù)均為負(fù)值時(shí)定義其最大子段和為 0。 ? 依此定義，所求的最優(yōu)值為： ? ? 例如，當(dāng) (a1,a2, a3, a4, a5,a6)=(2,11,4,13,5,2)時(shí)，最大子段和為： ? ?????? ?????jikknji a1 m a x,0m a x? ? 202241142???????kka1. 一個(gè)簡(jiǎn)單算法 ? 一個(gè)簡(jiǎn)單算法： int MaxSum(int n, a, amp。besti, amp。bestj) { int sum=0。 for(i=1。i=n。i++) for(j=1。j=n。j++){ int thissum=0。 for(k=i。k=j。k++) thissum+=a[k]。 if(thissumsum){ sum=thissum。 besti=i。 bestj=j。} } return sum。 } ? 算法有 3重循環(huán)，復(fù)雜性為 O(n3)。 ? 由于有： ? 算法可作如下改進(jìn)： int MaxSum(int n, a, amp。besti, amp。bestj) { int sum=0。 for(i=1。i=n。i++){ int thissum=0。 for(j=i。j=n。j++){ thissum+=a[j]。 if(thissumsum){ sum=thissum。 besti=i。 bestj=j。 } } } } ? 改進(jìn)后的算法復(fù)雜性為 O(n2) 。 ?? ?????1jikkjjikk aaa2. 分治方法求解 ? 從問題的解的結(jié)構(gòu)可以看出，它適合于用分治策略求解： ? 如果將所給的序列 a[1:n]分為長(zhǎng)度相等的兩段a[1:n/2]和 a[n/2+1:n]，分別求出這兩段的最大子段和，則 a[1:n]的最大子段和有三種情形： A. a[1:n]的最大子段和與 a[1:n/2]的最大子段和相同； B. a[1:n]的最大子段和與 a[n/2+1:n]的最大子段和相同； C. a[1:n]的最大子段和為下面的形式 。 ???????????????????nnkkninnikknijikk asasnjnniaC121222211 m a xm a x12,21,.2. 分治方法求解 ? A、 B這兩種情形可遞歸求得。對(duì)于情形 C，容易看出，a[n/2]與 a[n/2+1]在最優(yōu)子序列中。因此，我們可以在a[1:n/2]和 a[n/2+1:n]中分別計(jì)算出如下的 s1和 s2。則s1+s2即為出現(xiàn)情形 C時(shí)的最優(yōu)值。 ? ? 從而設(shè)計(jì)出下面所示的分治算法。 ???????????????????nnkkninnikknijikk asasnjnniaC121222211 m a xm a x12,21,.int MaxSubSum(int a, int left, int right) { int sum=0。 if (left==right)sum=a[left]0?a[left]:0。 else{int center=(left+right)/2。 int leftsum=MaxSubSum(a,left,center)。 int rightsum=MaxSubSum(a,center+1,right)。 int s1=0。lefts=0。 for (int i=center。i=left。i) { lefts+=a[i]。 if (leftss1) s1=lefts。 } int s2=0。rights=0。 for (int i=center+1。i=right。i++) { rights+=a[i]。 if (rightss2) s2=rights。 } sum=s1+s2。 if (sumleftsum) sum=leftsum。 if (sumsightsum) sum=rightsum。 } return sum。 } ? ?? ?? ?? ? ? ?nnOnTnOnTOnTl o g221????????????????復(fù)雜性分析：3. 動(dòng)態(tài)規(guī)劃方法求解 ? 在對(duì)上述分治算法的分析中我們注意到， ? 由 bj的定義易知，當(dāng) bj10時(shí) bj=bj1+aj，否則 bj=aj。由此可得計(jì)算 bj的動(dòng)態(tài)規(guī)劃遞歸式 bj=max{bj1+aj， aj}， 1≤j≤n。 ? 據(jù)此，可設(shè)計(jì)出求最大子段和的動(dòng)態(tài)規(guī)劃算法如下： int MaxSum(int n, int a) { int sum=0。 b=0。 for (i=1。i=n。i++) { if (b0) b+=a[i]。 else b=a[i]。 if (bsum) sum=b。 } return sum。 } ? 顯然該算法的計(jì)算時(shí)間為 O(n)。 jnjjikkjinjjkknjijikkjijbaanjab????????????????????????????111111m a xm a xm a xm a x1m a x 為，則所求的最大子段和，若
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1