专栏首页AI 算法笔记数据结构算法入门--一文了解什么是复杂度

数据结构算法入门--一文了解什么是复杂度

作者:TeroVesalainen

本文大约 3000 字,阅读大约需要 10 分钟

最近会开始更新一个数据结构算法的学习系列,同时不定期更新 leetcode 的刷题。

这是第一篇文章,在开始介绍各种数据结构和算法之前,先了解下什么是复杂度,包括时间复杂度和空间复杂度。

什么是复杂度分析

  1. 数据结构和算法解决是“如何让计算机更快时间、更省空间的解决问题”。
  2. 因此需从执行时间和占用空间两个维度来评估数据结构和算法的性能。
  3. 分别用时间复杂度和空间复杂度两个概念来描述性能问题,二者统称为复杂度。
  4. 复杂度描述的是算法执行时间(或占用空间)与数据规模的增长关系

为什么需要复杂度分析

  1. 和性能测试相比,复杂度分析有不依赖执行环境、成本低、效率高、易操作、指导性强的特点。
  2. 掌握复杂度分析,将能编写出性能更优的代码,有利于降低系统开发和维护成本。

如何进行复杂度分析

对于时间复杂度的分析,通常使用大O复杂度表示法,表示代码执行时间随数据规模增长的变化趋势,所以,也叫作渐进时间复杂度(asymptotic time complexity),简称时间复杂度

用公式表示,就是 T(n) = O(f(n))表示,其中 T(n) 表示算法执行总时间,f(n) 表示每行代码执行总次数,而 n 表示数据的规模。

由于时间复杂度描述的是算法执行时间与数据规模的增长变化趋势,所以常量阶、低阶以及系数实际上对这种增长趋势不产决定性影响,所以在做时间复杂度分析时可以忽略这些项。

具体分析的时候,有下列三个方法:

  1. 单段代码只看循环次数最多的部分
  2. 多段代码取复杂度最高的:即有个多个循环,但只看循环次数量级最高的那段代码
  3. 乘法法则--嵌套代码进行乘积:多个循环嵌套,就是相乘

常见的时间复杂度

按照数量级递增,常见的时间复杂度量级有:

  • 常量阶 O(1)
  • 对数阶 O(logn)
  • 线性阶 O(n)
  • 线性对数阶 O(nlogn)
  • 平方阶 O(n^2),立方阶 O(n^3)…k次阶 O(n^k)
  • 指数阶 O(2^n)
  • 阶乘阶 O(n!)

其中,最后两种情况是非常糟糕的情况,当然 O(n^2) 也是一个可以继续进行优化的情况。

接下来简单介绍上述复杂度中的几种比较常见的:

O(1)

O(1) 表示的是常量级时间复杂度,也就是只要代码的执行时间不随 n 的增大而增长,都记作 O(1) 。一般只要算法不包含循环语句和递归语句,时间复杂度都是 O(1)

像下列代码,有 3 行,但时间复杂度依然是O(1),而非 O(3)

a = 3
b = 4
print(a + b)
O(logn)、O(nlogn)

O(logn) 也是一个常见的时间复杂度,下面是一个 O(logn) 的代码例子:

i = 1
count = 0
n = 20
while i <= n:
    count += 1
    i *= 2
print('while 循环运行了 {} 次'.format(count))

这段代码其实就是每次循环都让变量 i 乘以 2,直到其大于等于 n,这里我设置 n=20,然后运行了后,输出结果是循环运行了 5 次。

实际上这段代码的结束条件,就是求 2^x=n 中的 x 是等于多少,那么循环次数也就知道了,而求 x 的数值,方法就是

,那么时间复杂度就是

假如上述代码进行简单的修改,将 i *= 2 修改为 i *= 3 ,那么同理可以得到时间复杂度就是

但在这里,无论是以哪个为对数的底,我们都把对数阶的时间复杂度记为 O(logn)

这里主要原因有两个:

  1. 对数可以互换,比如

,也就是

,常量

  1. 基于前面的理论,系数可以被忽略,也就是这里的常量 C 可以忽略

基于这两个原因,对数阶的时间复杂度都忽略了底,统一为 O(logn)

至于 O(nlogn) ,根据乘法法则,只需要将对数阶复杂度的代码,运行 n 次,就可以得到这个线性对数阶复杂度了。

注意, O(nlogn) 是非常常见的时间复杂度,常用的排序算法如归并排序、快速排序的时间复杂度都是 O(nlogn)

O(m+n)、O(m*n)

前面介绍的情况都是只有一个数据规模 n ,但这里介绍有两个数据规模的情况--mn

# O(m+n)
def cal(n, m):
    result = 0
    for i in range(n):
        result += i

    for j in range(m):
        result += j * 2

    return result

简单的代码示例如上述所示,如果事先无法评估 mn 的量级大小,那么这里的时间复杂度就没法选择量级最大的,所以其时间复杂度就是 O(m+n)

同理,对于嵌套循环,就是 O(m*n) 的时间复杂度了。

最好、最坏、平均、均摊时间复杂度

这四种复杂度的定义如下:

  • 最好情况时间复杂度:代码在最理想的情况下执行的时间复杂度;
  • 最坏情况时间复杂度:代码在最坏情况下执行的时间复杂度;
  • 平均情况时间复杂度:代码在所有情况下执行的次数的加权平均值表示
  • 均摊时间复杂度:代码执行的所有复杂度情况中,绝大多数都是低级别的复杂度,个别情况会发生最高级别复杂度且发生具有时序关系时,可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊复杂度就等于低级别复杂度,也可以看作是特殊的平均时间复杂度。

为什么会有这四种复杂度呢?原因是:

同一段代码在不同情况下时间复杂度会出现量级差异,为了更全面、更准确描述代码的时间复杂度,引入这四种复杂度的概念;

但通常除非代码是出现量级差别的时间复杂度,才需要区分这四种复杂度,大多数情况都不需要区分它们。

下面是给出第一个代码例子:

# 在数组 arr 中查找目标数值 x
def find(arr, x):
    for val in arr:
        if val == x:
            return True
    return False

这个例子假设数组 arr 的长度是 n ,那么它最好的情况,就是第一个数值就是需要查找的 x ,此时复杂度是 O(1) ,但最坏情况就是最后一个数值或者不存在需要查找的 x ,那么此时就遍历一遍数组,复杂度就是 O(n) ,因此这段代码最好和最坏情况是会出现量级差别的,O(1)O(n) 分别是最好情况复杂度和最坏情况复杂度。

而这段代码的平均情况时间复杂度是 O(n) ,具体分析就是首先考虑所有可能的情况以及对应出现的概率,可能发生的情况先分为两种,存在和不存在需要查找的数值 x,也就是分别是 1/2 的概率,然后对于存在的情况下,又有 n 种情况,即出现在数组任意位置的概率都是均等的,那么它们的概率乘以存在的概率就是 1/2n ,接着再考虑每种情况需要搜索的元素个数,其实就是代码执行的次数,这个分别就是从 1 到 n,并且对于不存在的情况,也是 n ,需要遍历一遍数组才发现不存在,所以平均时间复杂度的计算过程如下:

计算得到的就是概率论中的加权平均值,也叫期望值,所以平均时间复杂度的全称应该叫加权平均时间复杂度或者期望时间复杂度

这里用大 O 表示法表示,并且去掉常量和系数后,就是 O(n)。

最后介绍下均摊时间复杂度,需要满足以下两个条件才使用:

1)代码在绝大多数情况下是低级别复杂度,只有极少数情况是高级别复杂度

2)低级别和高级别复杂度出现具有时序规律均摊结果一般都等于低级别复杂度

空间复杂度分析

和时间复杂度的定义类似,空间复杂度全称就是渐进空间复杂度(asymptotic space complexity),表示算法的存储空间与数据规模之间的增长关系

简单介绍下一个程序所需要的空间主要由以下几个部分构成:

  • 指令空间:是值用来存储经过编译之后的程序指令所需要的空间。
  • 数据空间:是指用来存储所有常量和变量值所需的空间。其主要由两个部分构成:
    • 存储常量和简单变量所需要的空间
    • 存储复合变量所需要的空间。这一类空间包括数据结构所需要的动态分配的空间
  • 环境栈空间:用来保存函数调用返回时恢复运行所需要的信息。例如,如果函数 fun1 调用了函数 fun2,那么至少必须保存 fun2 结束时 fun1 将要继续执行的指令的地址。

本系列主要参考极客时间上的数据结构与算法之美课程,目前这门课正在做活动,拼团只需 65 元,课程的设计非常合理,而且介绍得很详细,有对应的代码辅助理解,还有一个开源的 GitHub,目前已经有1w+的star了:

https://github.com/wangzheng0822/algo

本文分享自微信公众号 - 算法猿的成长(AI_Developer),作者:kbsc13

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

原始发表时间:2019-10-16

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • [GAN学习系列3]采用深度学习和 TensorFlow 实现图片修复(中)

    上一篇文章--[GAN学习系列3]采用深度学习和 TensorFlow 实现图片修复(上)中,我们先介绍了对于图像修复的背景,需要利用什么信息来对缺失的区域进行...

    kbsc13
  • Python基础入门_5面向对象基础

    第五篇主要介绍 Python 的面向对象基础知识,也就是类的介绍,包括类方法和属性、构造方法、方法重写、继承等,最后给出两道简单的练习题。

    kbsc13
  • [实战]制作简单的公众号二维码关注图

    最近刚刚更换了公众号名字,然后自然就需要更换下文章末尾的二维码关注图,但是之前是通过 windows 自带的画图软件做的,但是之前弄的时候其实还是比较麻烦的,所...

    kbsc13
  • 数据结构和算法

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

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

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

    触摸壹缕阳光
  • 昨天的文章,有朋友给出"更好的"解法,其实并不是...

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

    double
  • 02 复杂度分析_pythoner学习数据结构与算法系列

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

    诡途
  • 常用算法解析

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

    wangxl
  • 笔试常考题型之时间复杂度

    Zoctopus
  • 笔试常考题型之时间复杂度

    Zoctopus

扫码关注云+社区

领取腾讯云代金券