如何理解和使用时间复杂度和空间复杂度

1.0 前言

本篇文章主要解决如下问题：

1. 数据结构和算法之间有什么关系？为什么经常把它们放在一起来研究和分析呢？
2. 我们为什么要掌握和使用复杂度分析方法？和使用真实数据测试相比，它的优缺点是什么？
3. 有哪些常见的算法时间复杂度？它们之间的优劣顺序是怎样的？
4. 有哪些常见的算法空间复杂度？
5. 如何理解最好、最坏和平均时间复杂度？

1.1 复杂度分析方法

数据结构是解决数据如何存储的问题，算法是解决数据如何操作的问题。数据结构为算法服务，算法需要作用在特定的数据结构上。

讲到数据结构和算法，就不得不先理解和使用复杂度。

复杂度分析是衡量数据结构与算法好坏的分析方法，通过考量效率和资源消耗来对比不同数据结构和算法在特定场景下的优劣情况；一般我们会从时间复杂度和空间复杂度两个维度来进行分析。

为什么要使用复杂度这个概念，直接运行代码进行测试不可以吗？

• 测试结果会依赖于测试环境，不同的测试环境测试结果会不一样；
• 测试结果会受数据规模的影响很大，在极端情况下可能会得出与理论完全相反的结果；
• 真实数据测试的代价比较大，复杂度分析方法只要掌握和使用得当，就能粗略地估算执行效率，成本较小；

1.2 时间复杂度

一般时间复杂度的表示如下：

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

其中，T(n)代表数据量为n时算法的时间复杂度，是我们求解的目标；O是一个数学符号，表示T(n)和f(n)是呈线性关系；f(n)是一个关于数据量n的表达式，涵盖了代码中具体的运行时间复杂度。

比如，如下代码f(n)=1+2n，那么用O表示的话，就是O(1+2n)；

int sum = 0;
for (i=1; i< n; i++) {
    sum += i;
}

再比如下面的代码f(n)=1+n+2n^2，那么用O表示的话，就是O(1+n+2n^2)；

int sum = 0;
for (int i=1; i<n; i++) {
    for (int j=1; j<n; j++) {
        sum = i + j;
    }
}

采用O表示的时间复杂度并不是具体代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，称为渐进时间复杂度，简称为时间复杂度。

一般在分析时间复杂度的时候，我们会忽略f(n)表达式中的常量、低阶和系数，因为当n很大的时候，它们并不左右整个时间复杂度的增长趋势，比如上面的例子中，时间复杂度可以简化为O(n)和O(n^2)。

在实际使用中，我们有如下的一些原则来帮助你计算时间复杂度：

• 只关注循环执行次数最多的一段代码；

• 顺序代码中总复杂度等于前后量级最大的那段代码的复杂度；

• 嵌套代码中的复杂度等于内外循环复杂度的乘积；

• 如果复杂度受多个数据量的影响，那么就需要用多个数据量来表示复杂度；

  比如下面两份代码的时间复杂度应该表示为O(n+m)、O(n*m)。

  int sum = 0;
  for (i=1; i< n; i++) {
      sum += i;
  }
  for (j=1; j< m; j++) {
      sum += j;
  }
  

  int sum = 0;
  for (int i=1; i<n; i++) {
      for (int j=1; j<m; j++) {
          sum = i + j;
      }
  }
  

下面是在算法中常遇见的复杂度量级：

• 常量阶O(1)，代码的执行时间不随着数据量n的增大而增长；

• 对数阶O(logn);

  while(i <= n) {
      i *= 2;
  }
  

  i的增长其实是一个等比数列，2，4，8，16，……，n，那么到达n的次数其实就是对底数为2的logn求值；所有的对数复杂度都可以变化为O(logn)；

  对数阶时间复杂度是比较高效的，是我们优化算法的目标。需要注意的是对数阶的算法并不一定就比常数阶的差。比如二分查找算法中，需要在2^32 个数中查找某一个元素，那么时间复杂度是O(log2^32)=32，也就是说只要最多32次就能从这么多数据中找到目标元素，而常数阶O(100)=100，虽然是常数阶，但是要100次，所以此时反而常数阶比不上对数阶。

• 线性阶O(n)；

• 线性对数阶O(nlogn)；

• 平方阶O(n^{2)、立方阶(n}3)、k次方阶(n^k)；

• 指数阶O(2^n)；

• 阶乘阶O(n!)；

它们中的部分函数图形如下，一般如果算法时间复杂度为O(2^n)或者O(n!)，随着数据量n的增大，整个时间复杂度会急剧增加，这就是比较低效的算法，需要优化改进。

常见复杂度函数图形

1.3 空间复杂度

空间复杂度全称为渐进空间复杂度，表示算法的存储空间与数据规模n之间的增长关系。

一般比较常见的空间复杂度：

• O(1)
• O(n)
• O(n^2)

对数阶和线性对数阶的空间复杂度一般很少见。

1.4 最好、最坏情况时间复杂度

比如下面这段代码：

int find(int[] array, int n, int target) {
    int position  = -1;
    for(int i=0; i<n; i++) {
        if(array[i] == target) {
            position = i;
            break;
        }
    }
    return position;
}

如上这段代码的含义是在长度为n的数组中，找到target元素的位置并返回。

然而在实际的查找过程中，有最好和最坏之分，最好的情况就是数组的第一个元素就是target，那么时间复杂度就是O(1)；最坏的情况就是target是数组的最后一个元素，或者根本不存在数组中，那么时间复杂度就是O(n)。

1.4 平均时间复杂度

平均情况下需要花费的时间复杂度，需要考虑每种情况出现的概率，然后乘以各自需要耗费的时间，最终求和得出。

一般情况下，我们并不需要区分最好、最坏和平均时间复杂度，只有当同一块代码在不同情况下，时间复杂度存在量级上的差距时，我们才会使用这三个指标来同时表示。