序言
對(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ī)算法幾乎是完美的算法。
當(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);