算法之路(一)----求最大子序列

序言

對(duì)于IT行業(yè)者來(lái)說(shuō)是趴,剛參加工作涛舍,還能找點(diǎn)借口,說(shuō)自己不擅長(zhǎng)算法唆途「谎牛可是工作三年以上的IT開(kāi)發(fā)者掸驱,還說(shuō)自己不會(huì)算法,不會(huì)設(shè)計(jì)模式就說(shuō)不過(guò)去了没佑。所以最近開(kāi)始擼算法和設(shè)計(jì)模式毕贼,重新開(kāi)一個(gè)集記錄算法的學(xué)習(xí)之路。算法在用戶(hù)量比較少图筹,或者計(jì)算量比較小的時(shí)候帅刀,影響確實(shí)不大,但是到達(dá)一定數(shù)量級(jí)的時(shí)候远剩,算法的優(yōu)劣就會(huì)極大的影響程序的順暢程度扣溺。優(yōu)秀的算法甚至能給人amazing的感覺(jué)。?

今天記錄《數(shù)據(jù)結(jié)構(gòu)與算法分析——C語(yǔ)言描述》中的一個(gè)求最大子序列的問(wèn)題瓜晤。

問(wèn)題

給定整書(shū)A1锥余,A2,……痢掠,AN(可能有負(fù)數(shù))驱犹,設(shè)整數(shù)k取值i到j(luò)(i<=j),求Ai到Aj的和的最大值(所有整數(shù)均為負(fù)數(shù),則最大子序列和為0)足画。?

例:?

輸入-2雄驹,11,-4淹辞,13医舆,-5,-2時(shí)象缀,答案為20(從A2到A4)蔬将。?

這個(gè)問(wèn)題比較有代表性,原因是因?yàn)榍蠼庠搯?wèn)題有多種算法央星,但是這些算法的性能又差異非常大霞怀。后面將記錄求解該問(wèn)題的四種算法。這四種算法在書(shū)上的運(yùn)行時(shí)間如下:



當(dāng)然隨著計(jì)算機(jī)設(shè)備的更新?lián)Q代莉给,現(xiàn)在的計(jì)算機(jī)運(yùn)行速度肯定沒(méi)這么慢毙石。后面會(huì)給出實(shí)際的運(yùn)行時(shí)間,還是先分析和記錄算法吧颓遏。

算法1

算法1是窮舉式的嘗試所有的可能胁黑,用三重嵌套for循環(huán)來(lái)求解最大子序列,但是運(yùn)行的時(shí)間非常慢州泊,時(shí)間復(fù)雜度是O(N*N*N),即N的立方漂洋。

- (int)maxSubsequenceSumFirst:(NSArray *)array

{

? ? int subSum, maxSum, i, j, k;

? ? NSInteger count = array.count;

? ? maxSum = 0;

? ? for (i = 0; i < count; i++) {

? ? ? ? for (j = i; j < count; j++) {

? ? ? ? ? ? subSum = 0;

? ? ? ? ? ? for (k = i; k <= j; k++) {

? ? ? ? ? ? ? ? subSum += [array[k] intValue];

? ? ? ? ? ? }


? ? ? ? ? ? if (subSum > maxSum) {

? ? ? ? ? ? ? ? maxSum = subSum;

? ? ? ? ? ? }

? ? ? ? }

? ? }

? ? return maxSum;

}

稍后一點(diǎn)經(jīng)驗(yàn)的開(kāi)發(fā)者遥皂,都可以看出最內(nèi)層的for循環(huán)力喷,其實(shí)有點(diǎn)多余,是可以省略的演训。因此就有了算法2弟孟。

算法2

算法2是在算法1的基礎(chǔ)上做了一些優(yōu)化,也比較簡(jiǎn)單样悟,因此就不做介紹了拂募。

- (int)maxSubsequenceSumSecond:(NSArray *)array

{

? ? int subSum, maxSum, i, j;

? ? NSInteger count = array.count;


? ? maxSum = 0;

? ? for (i = 0; i < count; i++) {

? ? ? ? subSum = 0;

? ? ? ? for (j = i; j < count; j++) {

? ? ? ? ? ? subSum += [array[j] intValue];


? ? ? ? ? ? if (subSum > maxSum) {

? ? ? ? ? ? ? ? maxSum = subSum;

? ? ? ? ? ? }

? ? ? ? }

? ? }

? ? return maxSum;

}

算法3

算法3采用一種分治策略。分治策略就是把問(wèn)題分成兩個(gè)大致相等的子問(wèn)題窟她,然后遞歸地對(duì)它們求解陈症,這是分的部分。治階段就是將兩個(gè)子問(wèn)題的解合并到一起并可能再做少量工作震糖,最后得到整個(gè)問(wèn)題的解录肯。?

該算法需要有一些分析:?

在例子中,最大子序列和可能出現(xiàn)在三處吊说。數(shù)據(jù)的左半部分论咏,數(shù)據(jù)的右半部分,或者跨越數(shù)據(jù)的中部颁井,左右兩半部分各占一些厅贪。前兩種情況可以用遞歸求解。第三種情況雅宾,需要加入一些計(jì)算养涮,可以通過(guò)求出前半部分包含最后一個(gè)元素的最大和,后半部分包含第一個(gè)元素的最大和秀又,然后將這兩個(gè)和加在一起单寂。

- (int)maxSubsequenceSumThird:(NSArray *)array{

? ? int right = (int)array.count - 1;

? ? return [self maxSubSum:array left:0 right:right];

}

- (int)maxSubSum:(NSArray *)array left:(int)left right:(int)right

{

? ? int maxLeftSum, maxRightSum;

? ? int maxLeftBorderSum, maxRightBorderSum;

? ? int leftBorderSum, rightBorderSum;

? ? int center, i;


? ? if (left == right) { //基本情況,左右相同吐辙,說(shuō)明只有一個(gè)元素? ? ? ? if (array[left] > 0) {

? ? ? ? ? ? return [array[left] intValue];

? ? ? ? } else {

? ? ? ? ? ? return 0;

? ? ? ? }

? ? }


? ? center = (left + right ) / 2;

? ? maxLeftSum = [self maxSubSum:array left:left right:center];

? ? maxRightSum = [self maxSubSum:array left:center + 1 right:right];


? ? maxLeftBorderSum = 0;

? ? leftBorderSum = 0;

? ? for (i = center; i >= left; i--) {

? ? ? ? leftBorderSum += [array[i] intValue];

? ? ? ? if (leftBorderSum > maxLeftBorderSum) {

? ? ? ? ? ? maxLeftBorderSum = leftBorderSum;

? ? ? ? }

? ? }


? ? maxRightBorderSum = 0;

? ? rightBorderSum = 0;

? ? for (i = center + 1; i <= right; i++) {

? ? ? ? rightBorderSum += [array[i] intValue];

? ? ? ? if (rightBorderSum > maxRightBorderSum) {

? ? ? ? ? ? maxRightBorderSum = rightBorderSum;

? ? ? ? }

? ? }


? ? int max = MAX(maxLeftSum, maxRightSum);


? ? return MAX(maxLeftBorderSum + maxRightBorderSum, max);

}

算法4

算法4也比較簡(jiǎn)短宣决,但是算法4必須要大量思考。?

分析:該算法首先定義兩個(gè)變量昏苏,maxSum用來(lái)記錄當(dāng)前求出的最大子序列和尊沸,subSum用來(lái)記錄遍歷的元素中非零和。如果subSum小于0贤惯,就將subSum重置為0洼专,因?yàn)楹竺婕词故钦龜?shù),也比不加上這個(gè)負(fù)數(shù)和要大孵构。當(dāng)出現(xiàn)subSum比之前記錄的maxSum大時(shí)屁商,就將其賦值給maxSum。一直遍歷到最后一個(gè)元素為止颈墅。

- (int)maxSubsequenceSumFourth:(NSArray *)array{

? ? int subSum, maxSum, j;

? ? subSum = maxSum = 0;


? ? for(j = 0; j < array.count ; j++) {

? ? ? ? subSum? += [array[j] intValue];


? ? ? ? if (subSum > maxSum) {

? ? ? ? ? ? maxSum = subSum;

? ? ? ? } else if (subSum < 0) {

? ? ? ? ? ? subSum = 0;

? ? ? ? }

? ? }


? ? return maxSum;

}

總結(jié)

優(yōu)秀的算法蜡镶,往往需要我們自己的思考和分析也更多。分析可以去掉一些不必要的計(jì)算官还,來(lái)減小運(yùn)算時(shí)間芹橡。?

算法4只對(duì)數(shù)據(jù)進(jìn)行一次掃描望伦,一旦Ai被讀入并被處理,它就不再需要被記憶屯伞。?

因此腿箩,如果數(shù)組在磁盤(pán)或磁帶上,它就可以被順序的讀入愕掏,在主存中不必存儲(chǔ)數(shù)組的任何部分度秘。不僅如此,在任意時(shí)刻饵撑,算法都能對(duì)它已經(jīng)讀入的數(shù)據(jù)給出子序列問(wèn)題的正確答案。就有這種特性的算法叫做聯(lián)機(jī)算法滑潘。?

僅需要常量空間并以線性時(shí)間運(yùn)行的聯(lián)機(jī)算法幾乎是完美的算法。

實(shí)際運(yùn)行時(shí)間

當(dāng)數(shù)組中元素的個(gè)數(shù)為10的時(shí)候:

2016-06-24 16:35:29.510 PractiseProject[4195:185619] 數(shù)組中元素的個(gè)數(shù):10

2016-06-24 16:35:29.510 PractiseProject[4195:185619] 算法一運(yùn)行時(shí)間:1.7808e-05 秒,計(jì)算結(jié)果:23

2016-06-24 16:35:29.510 PractiseProject[4195:185619] 算法二運(yùn)行時(shí)間:5.098e-06 秒,計(jì)算結(jié)果:23

2016-06-24 16:35:29.511 PractiseProject[4195:185619] 算法三運(yùn)行時(shí)間:8.092e-06 秒,計(jì)算結(jié)果:23

2016-06-24 16:35:29.511 PractiseProject[4195:185619] 算法四運(yùn)行時(shí)間:2.909e-06秒,計(jì)算結(jié)果:23


當(dāng)數(shù)組中元素的個(gè)數(shù)為28的時(shí)候(從上圖中语卤,可以看到算法2和算法3在30左右時(shí)會(huì)出現(xiàn)拐點(diǎn)):

2016-06-24 16:36:20.751 PractiseProject[4217:186946] 數(shù)組中元素的個(gè)數(shù):28

2016-06-24 16:36:20.751 PractiseProject[4217:186946] 算法一運(yùn)行時(shí)間:0.000150832 秒,計(jì)算結(jié)果:114

2016-06-24 16:36:20.751 PractiseProject[4217:186946] 算法二運(yùn)行時(shí)間:1.8889e-05 秒,計(jì)算結(jié)果:114

2016-06-24 16:36:20.751 PractiseProject[4217:186946] 算法三運(yùn)行時(shí)間:1.808e-05 秒,計(jì)算結(jié)果:114

2016-06-24 16:36:20.752 PractiseProject[4217:186946] 算法四運(yùn)行時(shí)間:3.782e-06 秒,計(jì)算結(jié)果:114


當(dāng)數(shù)組中元素的個(gè)數(shù)為100的時(shí)候:

2016-06-24 16:37:21.658 PractiseProject[4234:187666] 數(shù)組中元素的個(gè)數(shù):100

2016-06-24 16:37:21.663 PractiseProject[4234:187666] 算法一運(yùn)行時(shí)間:0.00419705 秒,計(jì)算結(jié)果:1204

2016-06-24 16:37:21.663 PractiseProject[4234:187666] 算法二運(yùn)行時(shí)間:0.000202042 秒,計(jì)算結(jié)果:1204

2016-06-24 16:37:21.663 PractiseProject[4234:187666] 算法三運(yùn)行時(shí)間:6.589e-05 秒,計(jì)算結(jié)果:1204

2016-06-24 16:37:21.664 PractiseProject[4234:187666] 算法四運(yùn)行時(shí)間:7.354e-06 秒,計(jì)算結(jié)果:1204


當(dāng)數(shù)組中元素的個(gè)數(shù)為1000的時(shí)候:

2016-06-24 16:38:00.642 PractiseProject[4249:188454] 數(shù)組中元素的個(gè)數(shù):1000

2016-06-24 16:38:04.816 PractiseProject[4249:188454] 算法一運(yùn)行時(shí)間:4.1736 秒,計(jì)算結(jié)果:32133

2016-06-24 16:38:04.829 PractiseProject[4249:188454] 算法二運(yùn)行時(shí)間:0.0124339 秒,計(jì)算結(jié)果:32133

2016-06-24 16:38:04.829 PractiseProject[4249:188454] 算法三運(yùn)行時(shí)間:0.00054806 秒,計(jì)算結(jié)果:32133

2016-06-24 16:38:04.829 PractiseProject[4249:188454] 算法四運(yùn)行時(shí)間:3.9842e-05 秒,計(jì)算結(jié)果:32133


當(dāng)數(shù)組中元素的個(gè)數(shù)為10000的時(shí)候(吃飯30分鐘回來(lái)后追逮,算法1還未計(jì)算出結(jié)果):

2016-06-24 16:39:03.479 PractiseProject[4265:189178] 數(shù)組中元素的個(gè)數(shù):10000

2016-06-24 16:38:04.816 PractiseProject[4249:188454] 算法一運(yùn)行時(shí)間:NA,計(jì)算結(jié)果:未知

2016-06-24 16:39:04.714 PractiseProject[4265:189178] 算法二運(yùn)行時(shí)間:1.23446 秒,計(jì)算結(jié)果:852859

2016-06-24 16:39:04.719 PractiseProject[4265:189178] 算法三運(yùn)行時(shí)間:0.00523675 秒,計(jì)算結(jié)果:852859

2016-06-24 16:39:04.720 PractiseProject[4265:189178] 算法四運(yùn)行時(shí)間:0.000379842 秒,計(jì)算結(jié)果:852859


當(dāng)數(shù)組中元素的個(gè)數(shù)為100000的時(shí)候:

2016-06-24 16:40:36.132 PractiseProject[4284:190117] 數(shù)組中元素的個(gè)數(shù):100000

2016-06-24 16:38:04.816 PractiseProject[4249:188454] 算法一運(yùn)行時(shí)間:NA,計(jì)算結(jié)果:未知

2016-06-24 16:42:40.983 PractiseProject[4284:190117] 算法二運(yùn)行時(shí)間:124.846 秒,計(jì)算結(jié)果:14896405

2016-06-24 16:42:41.046 PractiseProject[4284:190117] 算法三運(yùn)行時(shí)間:0.0624209 秒,計(jì)算結(jié)果:14896405

2016-06-24 16:42:41.049 PractiseProject[4284:190117] 算法四運(yùn)行時(shí)間:0.00294211 秒,計(jì)算結(jié)果:14896405


補(bǔ)充

生成隨機(jī)整數(shù)數(shù)組的方法:

/**?*? 生成一個(gè)有count個(gè)元素的數(shù)組?*?* @paramcount 個(gè)數(shù)?*?* @return數(shù)組?*/- (NSArray *)arrayWithCount:(NSInteger)count

{

? ? NSMutableArray *array = [NSMutableArray arrayWithCapacity:count];

? ? if (count <= 0) {

? ? ? ? return array;

? ? }

? ? for (int i = 0; i < count; i++) {

? ? ? ? int number = arc4random() % count;

? ? ? ? int random = arc4random() % 2;

? ? ? ? if (random == 0) {

? ? ? ? ? ? number *= -1;

? ? ? ? }


? ? ? ? [array addObject:[NSNumber numberWithInt:number]];

? ? }


? ? return array;

}

統(tǒng)計(jì)運(yùn)行時(shí)間的過(guò)程:

int n = 100;

? ? NSArray *randomArray = [self arrayWithCount:n];

? ? NSLog(@"數(shù)組中元素的個(gè)數(shù):%d",n);

? ? CFTimeInterval startTime =? CACurrentMediaTime();

? ? int one = [self maxSubsequenceSumFirst:randomArray];

? ? CFTimeInterval endTime = CACurrentMediaTime();

? ? NSLog(@"算法一運(yùn)行時(shí)間:%g 秒,計(jì)算結(jié)果:%d", endTime - startTime, one);


? ? startTime =? CACurrentMediaTime();

? ? int two = [self maxSubsequenceSumSecond:randomArray];

? ? endTime = CACurrentMediaTime();

? ? NSLog(@"算法二運(yùn)行時(shí)間:%g 秒,計(jì)算結(jié)果:%d", endTime - startTime, two);


? ? startTime =? CACurrentMediaTime();

? ? int three = [self maxSubsequenceSumThird:randomArray];

? ? endTime = CACurrentMediaTime();

? ? NSLog(@"算法三運(yùn)行時(shí)間:%g 秒,計(jì)算結(jié)果:%d", endTime - startTime, three);


? ? startTime =? CACurrentMediaTime();

? ? int four = [self maxSubsequenceSumFourth:randomArray];

? ? endTime = CACurrentMediaTime();

? ? NSLog(@"算法四運(yùn)行時(shí)間:%g 秒,計(jì)算結(jié)果:%d", endTime - startTime, four);

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市粹舵,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌眼滤,老刑警劉巖巴席,帶你破解...
    沈念sama閱讀 217,826評(píng)論 6 506
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件诅需,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡堰塌,警方通過(guò)查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,968評(píng)論 3 395
  • 文/潘曉璐 我一進(jìn)店門(mén)场刑,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái),“玉大人,你說(shuō)我怎么就攤上這事恤煞∈嚎保” “怎么了居扒?”我有些...
    開(kāi)封第一講書(shū)人閱讀 164,234評(píng)論 0 354
  • 文/不壞的土叔 我叫張陵丑慎,是天一觀的道長(zhǎng)喜喂。 經(jīng)常有香客問(wèn)我竿裂,道長(zhǎng)玉吁,這世上最難降的妖魔是什么腻异? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 58,562評(píng)論 1 293
  • 正文 為了忘掉前任,我火速辦了婚禮悔常,結(jié)果婚禮上影斑,老公的妹妹穿的比我還像新娘机打。我一直安慰自己矫户,他們只是感情好残邀,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,611評(píng)論 6 392
  • 文/花漫 我一把揭開(kāi)白布。 她就那樣靜靜地躺著芥挣,像睡著了一般。 火紅的嫁衣襯著肌膚如雪空免。 梳的紋絲不亂的頭發(fā)上空另,一...
    開(kāi)封第一講書(shū)人閱讀 51,482評(píng)論 1 302
  • 那天鼓蜒,我揣著相機(jī)與錄音痹换,去河邊找鬼。 笑死都弹,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的畅厢。 我是一名探鬼主播,決...
    沈念sama閱讀 40,271評(píng)論 3 418
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼浦楣!你這毒婦竟也來(lái)了?” 一聲冷哼從身側(cè)響起振劳,我...
    開(kāi)封第一講書(shū)人閱讀 39,166評(píng)論 0 276
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤,失蹤者是張志新(化名)和其女友劉穎历恐,沒(méi)想到半個(gè)月后,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體弱贼,經(jīng)...
    沈念sama閱讀 45,608評(píng)論 1 314
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,814評(píng)論 3 336
  • 正文 我和宋清朗相戀三年吮旅,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片庇勃。...
    茶點(diǎn)故事閱讀 39,926評(píng)論 1 348
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖匪凉,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情再层,我是刑警寧澤贸铜,帶...
    沈念sama閱讀 35,644評(píng)論 5 346
  • 正文 年R本政府宣布聂受,位于F島的核電站,受9級(jí)特大地震影響蛋济,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜碗旅,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,249評(píng)論 3 329
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望祟辟。 院中可真熱鬧医瘫,春花似錦旧困、人聲如沸醇份。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 31,866評(píng)論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)。三九已至怖竭,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間侵状,已是汗流浹背赞弥。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 32,991評(píng)論 1 269
  • 我被黑心中介騙來(lái)泰國(guó)打工趣兄, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留悼嫉,地道東北人艇潭。 一個(gè)月前我還...
    沈念sama閱讀 48,063評(píng)論 3 370
  • 正文 我出身青樓戏蔑,卻偏偏與公主長(zhǎng)得像蹋凝,于是被迫代替她去往敵國(guó)和親总棵。 傳聞我的和親對(duì)象是個(gè)殘疾皇子鳍寂,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,871評(píng)論 2 354

推薦閱讀更多精彩內(nèi)容