数据结构和算法 时间复杂度 空间复杂度 大O表示法

数据结构和算法之美-第一篇-如何进行复杂度分析

Posted by Kylen on 2019-07-29

什么是复杂度分析

我们知道，数据结构和算法本身解决的问题是“快”和“省”的问题，，即如何让代码运行的更快，如何让程序更省存储空间。我们实际场景中通常需要综合考量现有的存储空间最大化执行效率。我们经常说的空间换时间，时间换空间就是一种综合考量。

“快”和“省”的问题也就是时间和空间的问题。所以复杂度分析就是分析代码的执行效率和占用存储空间的分析过程。具体也分为时间复杂度和空间度两个维度。

复杂度分析很重要，只有会进行复杂度分析，才能继续进行后续数据结构和算法的学习，感受不同结构和算法的差异。

为什么要进行复杂度分析

其实评判一段代码或程序好不好，最简单的方式就是跑一下，是骡子是马拉出来溜溜。这也是我平时开发常用的方式，普通常见的业务场景中不会出现重大性能问题，所以表象上给人的感觉就是还行、不慢。我想我就是在这种模式中避过了进步的机会。

这种方式也叫做事后统计法，它的弊端主要有两点：

  • 测试的结果依赖环境
    我日常使用Mac开发，程序在windows上运行效率明显没有在Mac上流畅。
  • 测试结果受数据规模影响较大
    数据规模一大，程序运行时间明显变长。
    受这些弊端影响，我们无法通过事后统计法来描述程序的执行效率和存储空间，因为不同环境、不同数据规模的结果是不一样的。

事后统计法是一样方式，也是一种评判标准。但我们只能拿来参考一下。

我们需要一个不用具体的测试数据来测试，就可以粗略地估计算法的执行效率的方法

也就是说，我们写完代码之后，甚至是在想代码怎么写的时候就已经大致知道了这段代码的复杂度。

如何进行复杂度分析

大O复杂度表示法

使用大O复杂度表示法，其中大O符号是一个渐进符号，是用于描述函数渐进行为的数学符号。我们可以用它来表示复杂度。

T(n) = O(f(n))

在这个表达式中，T(n)表示代码执行的时间；n表示数据规模；f(n)表示代码执行的总次数，是一个函数；大O表示代码的执行时间和f(n)表达式成正比。

举个栗子：

1
2
3
4
5
6
7
function foo(n) {
 let sum = 0;
 for (let i = 1; i <= n; ++i) {
   sum = sum + i
 }
 return sum;
}

从CPU的角度而言，这段代码每一行都执行这类似的操作：读数据-操作-写数据。我们假设每行代码执行时间都是一样的，为unit_time（单元时间），当然真正执行的时候每行代码的执行时间谁也没法预料，我们只需要粗略估计。

第2行代码执行了1次，第3、4行代码执行了n次，所以这段代码的执行时间为：(2n + 1) * unit_time，用大O复杂度表示法表示为：T(n) = O(2n + 1)

所以大O表示法其实并不表示一段代码真正的执行时间，而是一种趋势，代码执行时间随着数据规模增长的变化趋势，所以也叫渐进时间复杂度，简称复杂度。与之对应的空间维度也就是渐进空间复杂度，简称空间复杂度。

采用大O复杂度表示法的时候，比如在时间维度上，表示的是执行效率随数据规模增长的变化趋势。若是数据规模n增长到无穷大，有些东西我们就可以忽略掉了，常量 系数 低阶都是可以忽略的。上面那个例子也就变成了：T(n) = O(n)

在练习阶段，我们可以细细的分析每行代码的时间复杂度，然后再忽略非关键的部分，等到熟练了，我们很容易就能抓住最耗时的代码段，并快速解析它的时间复杂度，基本是秒出。并不会花费我们过多的时间。

复杂度量级

代码有千千万万种，复杂度量级并不多，下面的7种几乎包含了今后所有可能接触到的代码的复杂度量级。粗略的分为两类：多项式量级和非多项式量级，非多项式量级只有两个指数阶和阶乘阶，它们随着数据规模的增长时间复杂度成几何倍增长，若是写了“这种级别”的代码，可得好好思量一下了。
data-structures-algorithm 2019-07-29 下午3.39.13.jpg
是不是觉得很熟悉，这不就是我们高中数学课上学的各种函数嘛，包括它们随着n的增长的变化趋势
data-structures-algorithm 2019-07-29 下午3.44.13.jpg

我们着重讨论一下多项式量级的时间复杂度。

  • O(1)
    O(1)表示常量级时间复杂度，这种情况时间复杂度和数据规模n就没有关系了，通常一段代码中没有循环语句、没有递归，即使是成千上万行的代码，我们也只说它的时间复杂度是O(1)
    举个栗子：

    1
    2
    3
    let a = 1
    const b = 2
    let c = 3

    虽然有三条语句，我们也只说时间复杂度是O(1)

  • O(logn) O(nlogn)
    举个栗子：

    1
    2
    3
    4
    let i = 1
    while(i <= n){
      i = i * 2
    }

    这种情况下，要经过多少次循环呢，简单思考一下，假设经过x次循环满足条件，不就是 2x > n，求值可得 x = log2n，呵，简单的数学运算。根据规则我们忽略参数，所以时间复杂度就是O(logn)，O(nlogn)可想而知就是n（2n等等）次logn，可能就是while外层套一个for循环。

  • O(n)
    这个基本不用说了，太常见了，看例子，for循环

    1
    2
    3
    4
    let s = 0
    for(let i=0; i<n; i++){
      s += i
    }

  • O(m + n) O(m * n)
    有些情况数据规模可能不唯一，O(m * n)，这种其实也不难分析，特地留意一下即可

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    function foo(m, n){
      let s1 = 0
      let s2 = 0
      for(let i = 0; i < m; i++){
        s1 += i
      }
      for(let i = 0; i < n; i++){
        s2 += i
      }
      return s1 + s2
    }

    时间复杂度为：O(m + n)

复杂度分析会贯穿整个数据结构和算法的学习体系，掌握它是重中之重，好在它本身也不是很难，多练几遍就会了。

空间复杂度

前面一直在说时间复杂度，空间复杂度同样可以使用大O表示法表示。空间复杂度分析起来远比时间复杂度要简单。举个栗子：

1
2
3
4
5
6
7
function foo(n){
  const a = []
  for(let i=0; i < n; i++){
    a.push(i)
  }
  return a
}

let i = 0;空间复杂度为1，a最终存储空间为n，所以最终空间复杂度为O(n)。常见的空间复杂度：O(1) O(n) O(n2) ，掌握这些基本就够了。

FEATURED TAGS
数据结构和算法 时间复杂度 空间复杂度 大O表示法
FRIENDS