复杂度分析的套路及常见的复杂度

栏目: IT技术 · 发布时间: 4年前

内容简介:本篇文章收录于专辑:你好,我是彤哥,一个每天爬二十六层楼还不忘读源码的硬核男人。

复杂度分析的套路及常见的复杂度

前言

本篇文章收录于专辑: http://dwz.win/HjK ,点击解锁更多数据结构与算法的知识。

你好,我是彤哥,一个每天爬二十六层楼还不忘读源码的硬核男人。

上一节,我们一起学习了表示复杂度的几个符号,我们说,通常使用大O来表示算法的复杂度,不仅合理,而且书写方便。

那么,使用大O表示法评估算法的复杂度有没有什么套路呢?以及常见的复杂度有哪些呢?

本节,我们就来解决这两个问题。

前情回顾

在正式讲解套路之前,我们先回忆一下前面几节讲到的内容。

在第2节,我们学习了渐近分析法,将算法的复杂度与输入规模挂钩,随着输入规模的增大,算法执行的时间将呈现一种什么样的趋势,将这个趋势用函数表示,再去除低阶项和常数项,就得到了算法的时间复杂度。

在第3节,我们分别从最坏、平均、最好三种情况来分析了算法的复杂度,得出结论,一般使用最坏情况来评估算法的复杂度。

在第4节,我们通过动态数组的插入元素及经典快速 排序 的时间复杂度,解释了有的时候不能使用最坏情况来评估算法的复杂度。

在第5节,我们从读音、数学、通俗理解三个方面分析了各种表示算法复杂度的符号,得出结论还是使用大O比较香,大O代表了算法的上界,它与前面讲到的最坏情况往往是对应的。

所以,这里所说的套路也是针对大部分情况,也就是最坏情况,对于一些个例,比如经典快排,我们虽然也是使用大O表示他们的复杂度,但是,其实是一种均摊的复杂度。

好了,让我们看看计算算法复杂度的套路到底是什么吧。

套路

我将计算算法复杂度的套路归纳为以下五步:

  1. 明确输入规模n;
  2. 考虑最坏情况或均摊情况,如果最坏情况为个例,那就是均摊;
  3. 计算算法执行的次数与n的关系,并用函数表示出来;
  4. 去除低阶项;
  5. 去除常数项;

比如,对于在数组中查找指定元素的操作:

  1. 输入规模为数组的长度n;
  2. 考虑最坏情况为目标元素不在数组中;
  3. 算法的执行次数为遍历所有数组元素,也就是n次,用函数表示f(n) = n;
  4. 去除低阶项,没有低阶项,还是n;
  5. 去除常数项,没有常数项,还是n;

所以,在数组中查找指定元素的时间复杂度为O(n)。

OK,使用这种方式可以很快的计算出算法的复杂度,也不需要进行额外的计算,非常快捷高效。

常见的复杂度

上面我们说了,复杂度的计算就是计算与输入规模n的关系,所以,我们想想数学中关于n的函数就能得出常见的复杂度了,我绘制了一张表格:

与n的关系 英文释义 复杂度 示例
常数(不相关) Constant O(1) 数组按索引查找元素
对数相关 Logarithmic O(logn) 二分查找
线性相关 Linear O(n) 遍历数组的元素
超线性相关 Superlinear O(nlogn) 归并排序、堆排序
多项式相关 Polynomial O(n^c) 冒泡排序、插入排序、选择排序
指数相关 Exponential O(c^n) 汉诺塔
阶乘相关 Factorial O(n!) 行列式展开
n的n次方 O(n^n) 不知道有没有这种算法

在这张表中,复杂度是依次增加的,可以看到常数复杂度O(1)无疑是最好的,让我们用一张图来直观感受下:

复杂度分析的套路及常见的复杂度

后记

本节,我们一起学习了复杂度分析的套路以及常见的复杂度,到目前为止,我们不管是举例还是讲解基本上都在说时间复杂度。

那么,空间复杂度又是什么呢?空间与时间之间如何权衡呢?

下一节,我们接着聊。

关注公号主“彤哥读源码”,解锁更多源码、基础、架构知识。


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

数字时代的营销战略

数字时代的营销战略

曹虎、王赛、乔林、【美】艾拉·考夫曼 / 机械工业出版社 / 2017-1 / 99.00元

菲利普•科特勒说,市场比市场营销变得更快(Market changes faster than Marketing),在这个变革的时代,从硅谷、波士顿到北京、上海、深圳,我们正在重新定义公司,重新定义组织,重新定义战略;同样地,营销亦需要重新定义。 从本质上讲,营销战略只有两个时代:实体时代与比特时代,也可称为工业时代与数字时代。从5年前开始,第二个时代正在向未来20年展开画卷,数字创新型企......一起来看看 《数字时代的营销战略》 这本书的介绍吧!

在线进制转换器
在线进制转换器

各进制数互转换器

RGB HSV 转换
RGB HSV 转换

RGB HSV 互转工具

HEX CMYK 转换工具
HEX CMYK 转换工具

HEX CMYK 互转工具