专栏首页彤哥读源码复杂度分析的套路及常见的复杂度

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

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

前言

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

上一节,我们一起学习了表示复杂度的几个符号,我们说,通常使用大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)无疑是最好的,让我们用一张图来直观感受下:

后记

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

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

下一节,我们接着聊。

本文分享自微信公众号 - 彤哥读源码(gh_63d1b83b9e01),作者:丹卿

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-07-25

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 什么情况下不能使用最坏情况评估算法的复杂度?

    上一节,我们从最坏、平均、最好三种情况分析了算法的复杂度,得出结论,通常来说,使用最坏情况来评估算法的复杂度完全够用了。

    彤哥
  • 到底什么才是真正的空间复杂度?

    现在有一个算法是这样的,给定一个数组,将数组中每个元素都乘以2返回,我实现了下面两种形式:

    彤哥
  • O、Θ、Ω、o、ω,别再傻傻分不清了!

    前面几节,我们一起学习了算法的复杂度如何分析,并从最坏、平均、最好以及不能使用最坏情况全方位无死角的剖析了算法的复杂度,在我们表示复杂度的时候,通常使用大O来表...

    彤哥
  • 算法(3)

    Dwyane
  • 算法笔记(八):复杂度分析(二)

    #感兴趣的可以去订阅极客时间前谷歌工程师的专栏:数据结构与算法之美,个人觉得写的很不错。这里只是我自己做的一个简单的笔记

    free赖权华
  • 02 复杂度分析_pythoner学习数据结构与算法系列

    设计算法时,时间复杂度要比空间复杂度更容易出问题,所以一般情况一下我们只对时间复杂度进行研究。一般面试或者工作的时候没有特别说明的话,复杂度就是指时间复杂度...

    诡途
  • 昨天的文章,有朋友给出"更好的"解法,其实并不是...

    昨天推送一道题目分析,一方面学习一个颇具特色的数组,它的取值不大于数组长度;另一方面通过这道题充分体会算法分析、逻辑推理的重要性。只有做好充分的分析,才可能写出...

    double
  • 数据结构与算法 1-4 常见时间复杂度与大小关系

    本系列是我在学习《基于Python的数据结构》时候的笔记。本小节主要介绍一些常见的时间复杂度以及它们之间的大小关系。

    触摸壹缕阳光
  • 常用算法解析

    算法基础:概念,时间复杂度,空间复杂度,常见算法以及复杂度计算 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?...

    wangxl
  • 数据结构和算法

    10个算法:递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法。

    分母为零

扫码关注云+社区

领取腾讯云代金券