算法基础_分析算法复杂度

1 算法

1.1 首先,什么是算法,我们一般这么定义算法:

算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令 ,算法代表着用系统的方法描述解决问题的策略机制。

也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出,所以,如果一个算法需要的时间或者控件是无限制的,那么这种算法我们认为是不可行的。

1.2 时间复杂度

一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n))为算法的渐进时间复杂度(O是数量级的符号 ),简称时间复杂度。

1.3 空间复杂度

这就不说空间复杂度了,一般我们分析一个算法只需要分析它的时间复杂度就行了。因为很少很少会存在一种算法说时间复杂度很低,控件复杂度很高的。也就是说,算法在很短的时间内,生成了大量的数据,而对于一个算法,这大量的数据基本就是中间数据,冗余数据。那这样的算法本身就存在着不合理性。

我们这里以基础的插入排序和归并排序来举例,来讲解一下如何分析算法的复杂度。这里以比较简单的排序来举例,是因为经典排序非常经典,使用的也很多,并且比较好分析它的算法复杂度。

2 插入排序

2.1 插入排序原理

这里引用百度百科里面的描述: 描述: 一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下: ⒈ 从第一个元素开始,该元素可以认为已经被排序 ⒉ 取出下一个元素,在已经排序的元素序列中从后向前扫描 ⒊ 如果该元素(已排序)大于新元素,将该元素移到下一位置 ⒋ 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置 ⒌ 将新元素插入到下一位置中 ⒍ 重复步骤2~5

这个过程好比我们打牌的时候,摸牌的动,每次将一个元素插入到一个已排好序的数组中,这个还是很形象的。(图来自于《算法导论》)

image

2.2 插入排序伪代码

使用伪代码的话,在《算法导论》一书中写作如下:

image

这个意思很明显,这段伪代码的风格和很多语言都相似,如果你曾经学过点C,C++,OC,Ruby,Python,Java什么的,应该都会看的懂。

2.3 插入排序OC代码

由于我是写iOS的,我这里就以OC来实现,另外最近在学习Python,我会在文章最后附带上一个Python3的版本(只为理解算法,不要苛求是否简洁)。

//OC 插入排序
- (NSArray *)insertSortWithArray:(NSArray *)array
{
    if (array.count <= 1)
    {
        return array;
    }
    NSMutableArray *_mutableArray = [NSMutableArray arrayWithArray:array];
    for (int i = 0; i < array.count; i++)
    {
        for (int j = i; j > 0; j--)
        {
            if (_mutableArray[j] < _mutableArray[j-1])
            {
                [_mutableArray exchangeObjectAtIndex:j withObjectAtIndex:j-1];
            }
        }
    }
    return _mutableArray;
}

如果上面伪代码看起来比较排斥的话,这个OC版本的,你应该看懂了,那么,我们开始分析这个插入排序吧。

2.4 插入排序的算法分析

image

我们这里给出每条语句的执行时间和执行次数,例如第一条语句,每次的执行时间按为c1,这里总共执行了n次,那么,总的耗时为c1n。可能有人会问,第一条语句不是从2开始嘛,到n结束啊,应该是执行n-1次,而不是n次。但是这里执行到n之后,会再次返回到for循环去判断j+1是否大于A.length,所以会多执行一次,所以是n次。

第一条到第四条都是一样的,到第五条的时候情况就不一样了。我们无法知道这里的while循环会执行多少次,最好的情况和最坏的情况会相差很大,那么我们暂时把它记作tj次。那么第五条执行的次数也就是从j......n,总共image次。第六条和第七条类似。

从上面我们可以得到,整个插入排序所需要的总时间为:(这里记作T(n),T代表总运行时间,由于和n有关系,所以记作T(n))

image

在最坏的情况下,所有数据都是倒序排好的,那么循环需要执行的次数就是:

image

那么,总的运行时间可以简化为:

image

我们可以记作为:

T(n) = an2+bn+c

我们这里只分析最坏情况,而不分析最好情况,原因是我们了解到一个算法的最坏情况,那么这个算法在运行的时候就不会出现比最坏情况还差劲的情况。这样我们可以知道一个界限,理论上是不会超过这个界限的。

这里我们做出一个更加简化的抽象,因为很多时候我们真正关注的是运行时间的增长率,意思就是,在n增长的时候,运行时间会如何增长。比如,我们会把 an2+bn+c简化为an2,因为相比较而言,当n比较大的时候,真正重要的就只有an2,其他的低阶项已经不重要了。我们这里一样把高阶项的常系数去掉,记作θ(n2),这里的这个θ是《算法导论》里面的写法,国产的书里面一般写作O。

现在,我们知道了一个插入排序的算法复杂度的计算方式。

3 算法运行时间描述记号

那么,下面解释一下《算法导论》里面描述算法运行时间的一些记号:(可参考《算法导论第三章》)

image

参考上图,比较形象啊

(a) 如果f(n)的值在n0之后,c1g(n) <= fn <= c2g(n),那么我们记作θ(g(n))

(b) 如果(n)的值在n0之后,fn <= cg(n),那么我们记作O(g(n))

(c) 如果(n)的值在n0之后,cg(n) <= fn,那么我们记作Ω(g(n))

除了这三种写法之外,《算法导论》中还有另外两个符号:

image

但是这些符号基本只适用于《算法导论》这本书中。在国产的算法书中,基本只会出现O和o两种,也差不多相当于《算法导论》中的θ和O。

4 归并排序

4.1 归并排序原理

虽然归并排序完全遵循分治法,但是这里并讲解分治法,这不在我们讨论范畴之内,可能下个博客会比较系统的讲解一下分治法,以此引出其他几个常用排序算法。 归并算法的操作如下:(摘自《算法导论》)

分解:分解待排序的n个元素的序列或各具n/2个元素的两个子序列。

解决:使用归并排序递归的排序两个子序列。

合并:合并两个已排序的子序列以产生已排序的答案。

当排序的序列长度为1时,递归“开始回升”,在这种情况下不要任何工作,因为长度为1的每个序列都是已排好序的。

上面的话可能不是很容易明白,我们举个例子:

我们现在有8个数据:

5 2 4 7 1 3 2 6

很明显,这个数据是没有排好序的,那么我们依据分治法的原理,把它分割为两个,我们可以得到两组数据:

5 2 4 7 和 1 3 2 6

很明显,这个还是没有排好序,那么,我们再次把每组数据拆分成两组数据:

5 2 和 4 7 和 1 3 和 2 6

那么,我们在拆分一次的话,就会总共分为8组:

5 2 4 7 1 3 2 6

这8组中,每组只有一个数据,很明显,每组都已经排好序了(废话,就一个数字,当然排好了),我们按照次序把它合并起来,过程类似于下图:

image

首先,第一组的第一个数据和第二组的第一个数据合并在一起,5和2,2比5小,2先加到数组中,5再和第二组数据的第二个数据比,但是这只有一个,所以把5添加到数组。以此类推,就可以从8组数据组合为4组数据,然后是2组,最后就是排序的结果,这就是归并算法。这种算法很适用于排序的数据量比较大,需要花比较大的内存才能处理的时候,归并排序就可以牛逼了。

4.2 归并排序OC代码

下面附上OC版的插入排序代码:(Python3版本会在文章最后给出)

- (void)applicationDidFinishLaunching:(NSNotification   *)aNotification
{
    NSArray *_array = @[@1, @10, @4, @98, @37, @15, @100, @32, @66];
//    NSLog(@"%@", [self mergeSortWithArray:_array]);
}
//OC 归并排序 主程
- (NSArray *)mergeWithLeftArray:(NSArray *)leftArray rightArray:(NSArray *)rightArray
{
    int l = 0;
    int r = 0;
    NSMutableArray *_resultArray = [NSMutableArray array];
    while (l < leftArray.count &&
           r < rightArray.count)
    {
        if (leftArray[l] < rightArray[r])
        {
            [_resultArray addObject:leftArray[l]];
            l++;
        }
        else
        {
            [_resultArray addObject:rightArray[r]];
            r++;
        }
    }
    [_resultArray addObject:(leftArray.lastObject > rightArray.lastObject)? leftArray.lastObject:rightArray.lastObject];
    return _resultArray;
}
//OC 归并排序
- (NSArray *)mergeSortWithArray:(NSArray *)array
{
    if (array.count <= 1)
    {
        return array;
    }
    NSInteger _number = array.count/2;
    NSArray *_leftArray = [self mergeSortWithArray:
                               [array subarrayWithRange:NSMakeRange(0, _number)]];
    NSArray *_rightArray = [self mergeSortWithArray:
                            [array subarrayWithRange:NSMakeRange(_number, array.count-_number)]];
    return [self mergeWithLeftArray:_leftArray rightArray:_rightArray];

}

4.3 归并排序伪代码

使用递归的方式的话,归并排序可以写为:(我相信大家都学过递归)

image

4.4 插入排序算法分析

我们这个归并法中,默认全都是平均分成两等份的,那么归并排序的运行时间可以理解 为:

image

这里不讲怎么得出这个等式的,有兴趣的可以自己算一下,或者看一下《算法导论》中文版的P20。

下图展示了如何求解递归式的:

image

图中,b~d部分,逐渐展开整个递归式,每次展开的一层的运行时间为cn,这里总共运行了log2n+ 1次,记作lgn+1。那么这个lgN是如何算出来的呢?

我们这里假设n是2的幂,也就是

n = 2x

也就是

x = log2x = lgn

总共分解了x+1次,所以总次数为lgn+1

每次计算时间为cn, 总代价为 cn(lgn+1)

所以归并排序的时间复杂度为θ(nlgn)

5 附件

5.1 插入排序Python3

insert_sort.py

5.2 归并排序Python3

merge_sort.py

Article Published in on Algorithm

Article by 付军