算法晨光第一剑之复杂度分析

发表于 2020-09-09 分类于计算机技术，算法阅读次数：：

对于 coder 来说，实现一个功能、一个框架、一个项目当然是主要任务。但是作为一个有追求的 coder 来说，还有两个目标是要去一直追寻的，简单来说，一个是 “快”，一个是 “省”。让代码运行得更快，涉及到代码的执行效率问题；让代码运行时更节省内存等资源，涉及到代码执行时的资源消耗问题；对此 2 问题的分析标准，就是我们今天主要探索的时间复杂度 (评判效率) 和空间复杂度 (评判资源消耗)。

1 时间复杂度

其实我相信只要了解过算法的人对 时间复杂度 这个概念都不会陌生，本文中不必累述，我们一般使用 大 O 表示法 来表示一个算法的时间复杂度。比如下面这个算法：

int sum(int[] array) {
  int sum = 0;
  for (int i = 0; i < array.length() ; i++) {
    sum += array[i];
  }
  return sum;
}

上面这个对一个数组求和的简单算法的时间复杂度是 O (n)，表示执行完这个算法需要用 n 次计算单位。这里的计算单位一般来说是个抽象，我们没法说就是具体的一次 CPU tick，大家可以理解为应该是一个对于当前实际问题的最小解决时间单元，比如上面的例子就是两个数求和。

-最佳时间复杂度、最坏时间复杂度、平均时间复杂度

概念的东西我这就不多说了，这里只讨论些建在基础上的东西。对于一个算法的时间复杂度，我们要知道其实并不是一定的，比如对于链表的查找算法，你从头节点开始找，如果要找的元素就在第一位，那么 O (1) 的时间复杂度就 ok 了。但如果要找的元素根本就不在链表里，你妥妥地要找 O (n) 次才行。那么，我们说，O (1) 是这个算法的 最佳时间复杂度，O (n) 是这个算法的 最坏时间复杂度，O (2/n) 是此算法的 平均时间复杂度，这个很好理解。

-均摊时间复杂度

除此之外，还有另一种更高级也更科学的时间复杂度计算方法 – 均摊时间复杂度。不过理解起来也不难，均摊时间复杂度 其实就是各种复杂度基于出现概率的加权平均计算法，比如上面说的链表查询，就是把每种情况的出现概率 x 复杂度然后加权平均，比如要查找的元素出现在第一位的概念为 1/n，复杂度为 O (1)，我们则用 1/n * 1。要查找的元素出现在第 2 位，概率也是 1/n，复杂度为 O (2)，我们则用 1/n * 2，所以我们加权求和一下就是：
$$
{1 \over n} \times 1 + {2 \over n} \times 2 + \ldots + {n \over n} \times n = {(1 + 2 + \ldots + n) \over n} n = {(1 + n) \over 2} = O(n)
$$

所以，我们平常一般情况下说的复杂度其实指的就是 均摊时间复杂度，因为对各种情况做了概率的加权平均，所以理论上是最公平的。上面的推导方式并不复杂，但略繁琐，分析每个算法时我们都要这样计算一把是不太现实的。

2 常见算法的时间复杂度

上面介绍了几种时间复杂度的计算方法，在日常工作中老是这样去推导是不现实的事情，实际上，我们对一个算法进行时间复杂度分析是有方法、技巧的。

最常用的技巧就是 “眼神法” ^_^，实际上很多算法我们一眼就可以看出时间复杂度大概是多少，这里主要是观察循环次数。当有嵌套循环时，就用 乘法法则，比如最简单的冒泡排序，两层循环，复杂度为 O (n*n) = $O (n^2)$。

还有个比较复杂的 主定理 (Master theorem)，这个推导太难太复杂了，但其解决了对于各类递归算法的时间复杂度计算，我们只要记住结果即可。

算法	算法特点	时间复杂度	备注
二分查找算法	每次问题规模减半	$O (log n)$
二叉树遍历		$O (n)$
合并排序		$O (n log n)$
快速排序	随机选择待排序序列中的一个数作为划分问题的标准	$O (n log n)$	划分是否平均影响算法复杂度，最差情况下，复杂度为 $O (n ^ 2)$
冒泡排序	两层循环	$O (n^2)$

然后再附一个各复杂度的增长曲线：

software-algorithm-complexity

3 空间复杂度

空间复杂度 一般是指计算整个算法的辅助空间单元的个数，更具体而言，一般就是运行一个算法需要多少内存。通常来说，我们并不太关心空间复杂度，比方说我们常做的事 – “空间换时间” ^_^

但是，如果你把问题具体到内存的话还是有很多考究，特别是当你写的程序是运行在资源有限的移动设备或是访问量较大的后台服务。

空间复杂度的计算相比时间复杂度要简单些，但我们更重要的是把握两者的平衡，我记得《编程珠玑》第一章里就有关于空间复杂度与时间复杂度的平衡的问题，待我有空也将之总结出来。

在时间与空间复杂度的讨论中有个关于递归的问题比较有趣，这里也值得说说。

3.1 有关递归问题的讨论

在网上看很多人会说递归算法效率较低，其实当我们遇到这类说法时，应该自行多思考思考，为什么递归效率会低？

赞成这类观点的人想的是：递归，就是是函数再调用函数，我们知道函数调用是有成本的，而且一个函数如果不断地嵌套调用，就会导致不断有函数要入栈（我有篇文章介绍过函数调用的过程深入函数栈，有兴趣的可以看看）。那如果这个递归调用的层级很深的话，确实就会有栈溢出的危险。

所以，对于需要嵌套很多层的算法，使用递归看起来就不是一个明智的选择。

但是，我们又可以发现，使用递归可以让代码更简洁明了。比如树的遍历，用递归可以写出很简洁明了的代码，但是如果不用递归，本身实现的复杂度就会高些，更别说让别人看及后面的维护了。

所以，我们并不需要怕使用递归，一个是函数的出入栈并没有大家想的那样影响效率，很多语言也对此有优化的方案 (比如 C++ 的 inline 函数)。其次，我们使用什么算法前都需要对问题进行评估，在效率差别不大的前提下，尽量使用更简洁易懂好维护的代码。另外，对于递归的优化有一个讨论的比较多的优化 – 尾递归，值得我们了解下。

3.2 尾递归

尾递归 就是把一个依赖上一层环境(或者说上下文) 的递归转变为一个不依赖上一层环境的递归, 转变的方法就是把需要用到的环境通过参数传递给下一层。这样介绍起来听起来还是有点绕。也可以这样说，顾名思义，尾递归就是从最后开始计算，每递归一次就算出相应的结果，也就是说，函数调用出现在调用者函数的尾部，因为是尾部，所以根本没有必要去保存任何局部变量。最简单的判断就是递归调用后直接返回，就尾递归。

附录中有篇阮一峰的文章，介绍的很好深入函数栈。

概念不好理解没关系，尾递归是怎样优化递归的？不如看例子来理解，我们看一个普通的累加算法：

求 1 累加到 n 的总和 - 普通递归算法

def recsum(n):
  if n == 1:
    return n
  else:
    return n + recsum(n - 1)

上面是累加算法的普通递归实现，其运行函数栈状况如下：

recsum(5)
5 + recsum(4)
5 + (4 + recsum(3))
5 + (4 + (3 + recsum(2)))
5 + (4 + (3 + (2 + recsum(1))))
5 + (4 + (3 + (2 + 1)))
5 + (4 + (3 + 3))
5 + (4 + 6)
5 + 10
15

可以看出，因为每次递归都依赖于下层递归函数的结果，所以函数栈需要一直叠加，然后到最后一层计算出来后才层层返回，得出结果 15.

我们下面看看尾递归是如何优化的：

累加问题 - 尾递归算法

def recsumTail(n, temp=0):
  if n == 0:
    return temp
  else:
    return recsumTail(n - 1, temp + n)

可以看到，我们看看尾递归的栈状况：

recsumTail(5, 0)
recsumTail(4, 5)
recsumTail(3, 9)
recsumTail(2, 12)
recsumTail(1, 14)
recsumTail(0, 15)
15

可以看出，尾递归因为从最后开始计算，每层函数可以不用依赖下层的计算结果，因此可以调用完直接返回结果出栈，空间复杂度优化至 O (1)。

3.3 尾递归的思想

我们不妨来剖析下尾递归。我们先看看普通递归的问题究竟是什么：

┌────────┐ ┌────┐┌──────────────┐
│ f(n) = │ │n + ││    f(n-1)    │
└────────┘ └────┘└──────┬───────┘
              ┌────────┐▼ ┌─────────┐
              │(n-1) + │  │ f(n-2)  │
              └────────┘  └──┬──────┘
                   ┌────────┐▼ ┌─────────┐
                   │(n-2) + │  │ f(n-3)  │
                   └────────┘  └─────────┘
                            ...
                              │
                              ▼
                      ┌───────┐ ┌────────┐
                      │  2 +  │ │  f(1)  │
                      └───────┘ └────┬───┘
                                     ▼
                                 ┌───────┐
                                 │   1   │
                                 └───────┘

我们可以看到，就是因为普通递归每次的函数返回 return n + recsum (n - 1)，都包含一个临时计算结果，使得函数之间有了依赖。如果尾递归的思想就是把这个函数栈间的依赖变成参数，往后面传。所以现在让我们再回过头看 recsumTail (n, temp=0) 这个尾递归算法：

累加问题 - 尾递归算法

def recsumTail(n, temp=0):
  if n == 0:
    return temp
  else:
    return recsumTail(n - 1, temp + n)

recsumTail (n - 1, temp + n) 这个递归调用，就是把每次迭代的临时结果加起来，然后往下层函数传。从而解除了函数栈间的结果依赖。

这是我个人对尾递归的理解，要进行尾递归优化时，你们也可以学我一样先基于普通递归画出调用的逻辑图，然后基于临时变量做出优化。总之要注意一点就是递归调用后直接返回单个函数 (不能是表达式)，就尾递归。

这个优化可以给我们平时编译就算是写普通的业务代码带来许多启发，特别是使用函数式编程的兄弟～

3.4 附附附 - 斐波那契尾递归

我们来看看一个经典问题斐波那契数。如果使用普通递归，结果为：

斐波那契 - 普通递归解法

let Count = 0
function fib(N: number): number {
  console.log(`Calculate ${++Count} times`);
  if (N == 0)  return 0;
  else if (N == 1) return 1;
  else return fib(N - 1) + fib(N - 2)
};

结果：

结果

1 2	... Calculate 177 times

函数递归调用了 177 次。

画图分析：

  迭代层级  临时变量 1   临时变量 2
          （下一函数）（下下函数）
fib(5,      0,         1)
fib(4,      1,         1)
fib(3,      1,         2)
fib(2,      2,         3)
fib(1,      3,         5)

然后我们从中发现规律，写出尾递归算法

斐波那契 - 尾递归解法

let Count = 0
function fib(n: number, current = 0, next = 1): number {
  console.log(`Calculate ${++Count} times`);

  // param check
  if (n < 0) { console.log('Error input'); return -1; }

  if (n == 0) return current;
  else return fib(n - 1, next, current + next);
};

结果

1	Calculate 11 time o

函数递归调用了 11 次。

PS: 解斐波那契，比较好的方法是使用变量保存中间结果的方法。这里只是为了展示下尾递归的思路，并非此题最佳解法。