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

废话

对于IT行业者来说,刚参加工作,还能找点借口,说自己不擅长算法。可是工作三年以上的IT开发者,还说自己不会算法,不会设计模式就说不过去了。所以最近开始撸算法和设计模式,重新开一个集记录算法的学习之路。算法在用户量比较少,或者计算量比较小的时候,影响确实不大,但是到达一定数量级的时候,算法的优劣就会极大的影响程序的顺畅程度。优秀的算法甚至能给人amazing的感觉。 今天记录《数据结构与算法分析------C语言描述》中的一个求最大子序列的问题。

问题

给定整数A1,A2,……,AN(可能有负数),设整数k取值i到j(i<=j),求Ai到Aj的和的最大值(所有整数均为负数,则最大子序列和为0)。 例: 输入-2,11,-4,13,-5,-2时,答案为20(从A2到A4)。 这个问题比较有代表性,原因是因为求解该问题有多种算法,但是这些算法的性能又差异非常大。后面将记录求解该问题的四种算法。这四种算法在书上的运行时间如下:

1.png

2.png

当然随着计算机设备的更新换代,现在的计算机运行速度肯定没这么慢。后面会给出实际的运行时间,还是先分析和记录算法吧。

算法1

算法1是穷举式的尝试所有的可能,用三重嵌套for循环来求解最大子序列,但是运行的时间非常慢,时间复杂度是O(NNN),即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;
}

稍后一点经验的开发者,都可以看出最内层的for循环,其实有点多余,是可以省略的。因此就有了算法2。

算法2

算法2是在算法1的基础上做了一些优化,也比较简单,因此就不做介绍了。

- (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采用一种分治策略。分治策略就是把问题分成两个大致相等的子问题,然后递归地对它们求解,这是的部分。阶段就是将两个子问题的解合并到一起并可能再做少量工作,最后得到整个问题的解。 该算法需要有一些分析: 在例子中,最大子序列和可能出现在三处。数据的左半部分,数据的右半部分,或者跨越数据的中部,左右两半部分各占一些。前两种情况可以用递归求解。第三种情况,需要加入一些计算,可以通过求出前半部分包含最后一个元素的最大和,后半部分包含第一个元素的最大和,然后将这两个和加在一起。

- (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) { //基本情况,左右相同,说明只有一个元素
        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也比较简短,但是算法4必须要大量思考。 分析:该算法首先定义两个变量,maxSum用来记录当前求出的最大子序列和,subSum用来记录遍历的元素中非零和。如果subSum小于0,就将subSum重置为0,因为后面即使是正数,也比不加上这个负数和要大。当出现subSum比之前记录的maxSum大时,就将其赋值给maxSum。一直遍历到最后一个元素为止。

- (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;
}

总结

优秀的算法,往往需要我们自己的思考和分析也更多。分析可以去掉一些不必要的计算,来减小运算时间。 算法4只对数据进行一次扫描,一旦Ai被读入并被处理,它就不再需要被记忆。 因此,如果数组在磁盘或磁带上,它就可以被顺序的读入,在主存中不必存储数组的任何部分。不仅如此,在任意时刻,算法都能对它已经读入的数据给出子序列问题的正确答案。就有这种特性的算法叫做联机算法。 仅需要常量空间并以线性时间运行的联机算法几乎是完美的算法。

实际运行时间

当数组中元素的个数为10的时候:

2016-06-24 16:35:29.510 PractiseProject[4195:185619] 数组中元素的个数:10
2016-06-24 16:35:29.510 PractiseProject[4195:185619] 算法一运行时间:1.7808e-05 秒,计算结果:23
2016-06-24 16:35:29.510 PractiseProject[4195:185619] 算法二运行时间:5.098e-06 秒,计算结果:23
2016-06-24 16:35:29.511 PractiseProject[4195:185619] 算法三运行时间:8.092e-06 秒,计算结果:23
2016-06-24 16:35:29.511 PractiseProject[4195:185619] 算法四运行时间:2.909e-06 秒,计算结果:23

当数组中元素的个数为28的时候(从上图中,可以看到算法2和算法3在30左右时会出现拐点):

2016-06-24 16:36:20.751 PractiseProject[4217:186946] 数组中元素的个数:28
2016-06-24 16:36:20.751 PractiseProject[4217:186946] 算法一运行时间:0.000150832 秒,计算结果:114
2016-06-24 16:36:20.751 PractiseProject[4217:186946] 算法二运行时间:1.8889e-05 秒,计算结果:114
2016-06-24 16:36:20.751 PractiseProject[4217:186946] 算法三运行时间:1.808e-05 秒,计算结果:114
2016-06-24 16:36:20.752 PractiseProject[4217:186946] 算法四运行时间:3.782e-06 秒,计算结果:114

当数组中元素的个数为100的时候:

2016-06-24 16:37:21.658 PractiseProject[4234:187666] 数组中元素的个数:100
2016-06-24 16:37:21.663 PractiseProject[4234:187666] 算法一运行时间:0.00419705 秒,计算结果:1204
2016-06-24 16:37:21.663 PractiseProject[4234:187666] 算法二运行时间:0.000202042 秒,计算结果:1204
2016-06-24 16:37:21.663 PractiseProject[4234:187666] 算法三运行时间:6.589e-05 秒,计算结果:1204
2016-06-24 16:37:21.664 PractiseProject[4234:187666] 算法四运行时间:7.354e-06 秒,计算结果:1204

当数组中元素的个数为1000的时候:

2016-06-24 16:38:00.642 PractiseProject[4249:188454] 数组中元素的个数:1000
2016-06-24 16:38:04.816 PractiseProject[4249:188454] 算法一运行时间:4.1736 秒,计算结果:32133
2016-06-24 16:38:04.829 PractiseProject[4249:188454] 算法二运行时间:0.0124339 秒,计算结果:32133
2016-06-24 16:38:04.829 PractiseProject[4249:188454] 算法三运行时间:0.00054806 秒,计算结果:32133
2016-06-24 16:38:04.829 PractiseProject[4249:188454] 算法四运行时间:3.9842e-05 秒,计算结果:32133

当数组中元素的个数为10000的时候(吃饭30分钟回来后,算法1还未计算出结果):

2016-06-24 16:39:03.479 PractiseProject[4265:189178] 数组中元素的个数:10000
2016-06-24 16:38:04.816 PractiseProject[4249:188454] 算法一运行时间:NA,计算结果:未知
2016-06-24 16:39:04.714 PractiseProject[4265:189178] 算法二运行时间:1.23446 秒,计算结果:852859
2016-06-24 16:39:04.719 PractiseProject[4265:189178] 算法三运行时间:0.00523675 秒,计算结果:852859
2016-06-24 16:39:04.720 PractiseProject[4265:189178] 算法四运行时间:0.000379842 秒,计算结果:852859

当数组中元素的个数为100000的时候:

2016-06-24 16:40:36.132 PractiseProject[4284:190117] 数组中元素的个数:100000
2016-06-24 16:38:04.816 PractiseProject[4249:188454] 算法一运行时间:NA,计算结果:未知
2016-06-24 16:42:40.983 PractiseProject[4284:190117] 算法二运行时间:124.846 秒,计算结果:14896405
2016-06-24 16:42:41.046 PractiseProject[4284:190117] 算法三运行时间:0.0624209 秒,计算结果:14896405
2016-06-24 16:42:41.049 PractiseProject[4284:190117] 算法四运行时间:0.00294211 秒,计算结果:14896405

补充

生成随机整数数组的方法:

/**
 *  生成一个有count个元素的数组
 *
 *  @param count 个数
 *
 *  @return 数组
 */
- (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;
}

统计运行时间的过程:

    int n = 100;
    NSArray *randomArray = [self arrayWithCount:n];
    NSLog(@"数组中元素的个数:%d",n);
    CFTimeInterval startTime =  CACurrentMediaTime();
    int one = [self maxSubsequenceSumFirst:randomArray];
    CFTimeInterval endTime = CACurrentMediaTime();
    NSLog(@"算法一运行时间:%g 秒,计算结果:%d", endTime - startTime, one);
    
    startTime =  CACurrentMediaTime();
    int two = [self maxSubsequenceSumSecond:randomArray];
    endTime = CACurrentMediaTime();
    NSLog(@"算法二运行时间:%g 秒,计算结果:%d", endTime - startTime, two);
    
    startTime =  CACurrentMediaTime();
    int three = [self maxSubsequenceSumThird:randomArray];
    endTime = CACurrentMediaTime();
    NSLog(@"算法三运行时间:%g 秒,计算结果:%d", endTime - startTime, three);
    
    startTime =  CACurrentMediaTime();
    int four = [self maxSubsequenceSumFourth:randomArray];
    endTime = CACurrentMediaTime();
    NSLog(@"算法四运行时间:%g 秒,计算结果:%d", endTime - startTime, four);

算法学习之路的开篇就到这里啦,Have Fun!

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小小挖掘机

使用Tensorflow实现数组的部分替换

简单描述一下场景:对于一个二维的整型张量,假设每一行是一堆独立的数,但是对于每一行的数,都有一个设定好的最小值的。我们需要做的是,对于每一行,找到第一次小于最小...

4312
来自专栏CDA数据分析师

开工大吉:几个让你月薪3万+的excel神技能

来源:运营圈信息流广告 职场中经常会用到哪些函数? IF函数、SUMIF函数、VLOOKUP函数、SUMPRODUCT函数...... 小编总结了8个在工作中常...

3996
来自专栏Java 源码分析

枚举

​ 枚举就是尝试所有的可能性,尤其是当我们在确定一个问题是不是的这一类问题中尤其有用,例如说给一堆数,让我我们判断他们是不是素数,或者素数的数量的时候,这...

3196
来自专栏ml

错排公式

错排公式 百科名片 pala提出的问题: 十本不同的书放在书架上。现重新摆放,使每本书都不在原来放的位置。有几种摆法? 这个问题推广一下,就是错排问题: n个有...

4129
来自专栏ACM算法日常

海战(线段树)- HDU 4027

这一篇是典型的线段树算法,这个算法在日常工作中可能非常少见,因为可以被常规算法所取代,但是在问题达到一定数量级之后,常规算法是很难搞定类似问题的...

1052
来自专栏编程之旅

数据结构——最小生成树(C++和Java实现)

快要一整个月没有更新博客了,之前的几周每周都想着要写,但是最后时间还是排不开,最近的状态是一直在写代码,一直在怼工作的需求,顺便刷刷算法题,国庆则是没心没肺的玩...

3464
来自专栏数据小魔方

求和函数系列——sum函数家族

今天要跟大家分享的是一组求和函数系列——sum函数家族! excel中最长用到的求和函数就是sum函数系列了,sum函数系列一共有三组函数: sum sumif...

2884
来自专栏大数据

概率数据结构简介

在处理大型的数据集时,我们常常进行一些简单的检查,如稀有项(Unique items)的数量、最常见的项,以及数据集中是否存在某些指定的项。通常的做法是使用某种...

5516
来自专栏数据结构与算法

20:反反复复

20:反反复复 总时间限制: 1000ms 内存限制: 65536kB描述 Mo和Larry发明了一种信息加密方法。他们首先决定好列数,然后将信息(只包含字...

3858
来自专栏Leetcode名企之路

【Leetcode】54. 螺旋矩阵

给定一个包含 m x n 个元素的矩阵(m 行, n 列),请按照顺时针螺旋顺序,返回矩阵中的所有元素。 示例 1:

1372

扫码关注云+社区

领取腾讯云代金券