ds01-概論-陳越主編-數(shù)據(jù)結(jié)構(gòu)-資料下載頁(yè)
2025-07-25 19:01本頁(yè)面
【正文】 /* i， j 循環(huán)結(jié)束 */ /* 9*/ return MaxSum。 } T( N ) = O( N3 ) 教材 . 第 1章 概論 167。 4 應(yīng)用實(shí)例：最大子列和問(wèn)題 21/25 〖 舉例 〗 給定序列： {2,11,4,13,5,2}， 其最大子列為： {11,4,13}，和為 20。 算法 2 int MaxSubsequenceSum ( const int A[ ], int N ) { int ThisSum, MaxSum, i, j。 /* 1*/ MaxSum = 0。 /* 初始化最大子列和 */ /* 2*/ for( i = 0。 i N。 i++ ) { /* i是子列左端位置 */ /* 3*/ ThisSum = 0。 /* ThisSum是從 A[i]到 A[j]的子列和 */ /* 4*/ for( j = i。 j N。 j++ ) { /* j是子列右端位置 */ /* 5*/ ThisSum += A[ j ]。 /* 對(duì)于相同的 i，不同的 j，只要在 j1次循環(huán)的基礎(chǔ)上累加 1項(xiàng)即可 */ /* 6*/ if ( ThisSum MaxSum ) /* 如果剛得到的這個(gè)子列和更大 */ /* 7*/ MaxSum = ThisSum。 /* 則更新結(jié)果 */ } /* j循環(huán)結(jié)束 */ } /* i循環(huán)結(jié)束 */ /* 8*/ return MaxSum。 } T( N ) = O( N2 ) 第 1章 概論 167。 4 應(yīng)用實(shí)例：最大子列和問(wèn)題 22/25 算法 3 分治法 4 ?3 5 ?2 ?1 2 6 ?2 治 分 4 5 6 2 6 8 11 T ( N/2 ) T ( N/2 ) O( N ) T ( N ) = 2 T( N/2 ) + c N , T(1) = O(1) = 2 [2 T( N/22 ) + c N/2] + c N = 2k O(1) + c k N 此處 N/2k = 1 = O( N log N ) 結(jié)論對(duì) N ? 2k同樣正確 程序在教材 第 1章 概論 167。 4 應(yīng)用實(shí)例：最大子列和問(wèn)題 23/25 該算法的核心思想是基于下面的事實(shí)： 如果整數(shù)序列 {a1, a2, …, an}的最大和子列是 {ai, ai+1, …, aj} ，那么必定有 對(duì)任意 i ≤ l ≤ j 都成立。 因此，一旦發(fā)現(xiàn)當(dāng)前子列和為負(fù)，則可以重新開始考察一個(gè)新的子列。 .0?? ?l ik ka算法 4 “在線”算法 int MaxSubsequenceSum( const int A[ ], int N ) { int ThisSum, MaxSum, j。 /* 1*/ ThisSum = MaxSum = 0。 /* 2*/ for ( j = 0。 j N。 j++ ) { /* 3*/ ThisSum += A[ j ]。 /* 4*/ if ( ThisSum MaxSum ) /* 5*/ MaxSum = ThisSum。 /* 6*/ else if ( ThisSum 0 ) /* 7*/ ThisSum = 0。 } /* end forj */ /* 8*/ return MaxSum。 } T( N ) = O( N ) 序列 A[ ] 僅需 掃描一遍！ ?1 3 ?2 4 ?6 1 6 ?1 3 2 4 任何時(shí)刻 , “ 在線 ”算法都可以對(duì)已經(jīng)讀入的數(shù)據(jù)序列給出 正確的最大子列和答案 第 1章 概論 167。 4 應(yīng)用實(shí)例：最大子列和問(wèn)題 24/25 NA NA NA O( N ) O(N log N) O( N2 ) O( N3 ) 時(shí)間復(fù)雜性 4 3 2 1 算法 N =10 N =100 N =1,000 N =10,000 N =100,000 子列大小 ?上述 4種算法用于求最大子列和所需的運(yùn)行時(shí)間的比較 (單位：秒 ) 注 : 不包括輸入子列的時(shí)間 . NA – Not Acceptable, 不可接受的時(shí)間 第 1章 概論 167。 4 應(yīng)用實(shí)例：最大子列和問(wèn)題 25/25
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號(hào)-1