算法分析習(xí)題參考答案第五章

1、1最大子段和問題：給定整數(shù)序列，求該序列形如的子段和naaa21???jikka的最大值：???????????jikknjia1max0max1)已知一個簡單算法如下：intMaxsum(intnintaintff(inti=1isum)sum=sumabesti=ibestj=jreturnreturnsum試分析該算法的時間復(fù)雜性。2)試用分治算法解最大子段和問題，并分析算法的時間復(fù)雜性。3)試說明最大子段和問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)

2、，并設(shè)計一個動態(tài)規(guī)劃算法解最大子段和問題。分析算法的時間復(fù)雜度。（提示：令）1()max12jkijnkibjajn????????解：1）分析按照第一章，列出步數(shù)統(tǒng)計表，計算可得)(2nO2）分治算法：將所給的序列a[1:n]分為兩段a[1:n2]、a[n21:n]，分別求出這兩段的最大子段和，則a[1:n]的最大子段和有三種可能：①a[1:n]的最大子段和與a[1:n2]的最大子段和相同；②a[1:n]的最大子段和與a[n21:n]

3、的最大子段和相同；③a[1:n]的最大子段和為兩部分的字段和組成，即；jnjilnijaaaaa???????????????????????1223）設(shè)則最大子段和為max)(1?????jikkjiajb).(maxmaxmaxmaxmax11111jbaanjjikkjinjjikknjni????????????????max)(11211jjjjjjjaaaaaaaaajb????????????最大子段和實際就是.)()2(

4、)1(maxnbbb?要說明最大子段和具有最優(yōu)子結(jié)構(gòu)性質(zhì)，只要找到其前后步驟的迭代關(guān)系即可。)1(maxmaxmaxmaxmax)(1111111jjjjjikkjijjijjikkjikkjiaajbaaaaaaajb?????????????????????????????若；0)1(??jbjajbjb???)1()(若，。0)1(??jbjajb?)(因此，計算的動態(tài)規(guī)劃的公式為：)(jb.1)1(max)(njaajbjbjj