时间复杂度

Big O notation

时间复杂度经常使用 Big O notation 来表示。下面是常见的7种时间复杂度：

我们是不考虑系数的， O(1) 并不代表它的复杂度是1，有可能是2或3或4。因此只要是常数次，都表示为 O(1) 。如果是线性复杂度，也就是 O(n) 复杂度，它可能是运算了 n 次，也可能是运算了 2n 次。

我们如何得出这个时间复杂度？最直观的方式就是看这段代码它根据 n 的不同情况它会运行多少次。

上面的例子中，第一段代码 System.out.println("Hey - your input is:" + n); 无论 n 是多少都只会执行一次，因此它的时间复杂度为 O(1) 。

第二段代码三个 System.out.println 无论 n 是多少，它们都只会各执行一次，所以也就是总共执行 3 次，但是由于 Big O notation 是忽略常数项的，因此它的时间复杂度为 O(1) 。

上面的例子中第一段代码中，虽然只有 System.out.println 一个语句，但是当 n 为 10000 的时候，语句是会执行 10000 次的。由于随着 n 的不同，执行的次数也不同，所以这段代码的时间复杂度为 O(n) 。

第二段代码的话，由于嵌套了两层 for 循环，如果 n 为 10 的话， System.out.println 这个语句就会执行 n * n 次。所以它的时间复杂度为 。

看上面的例子中的第一段代码，我们求 i 与 n 的关系。

由于 Big O notation 是忽略系数，并且参考的是指数最高项，因此其实就是求 n 与 i 的关系，得到第一段代码的时间复杂度为 。

递归如何分析时间复杂度

分析递归的时间复杂度，重要的是要知道递归总共执行了多少次。如果是 for 循环的话是很好理解的，但是递归的话是层层嵌套下去的，直观地得出递归的时间复杂度并不容易。在分析递归的时间复杂度时，需要把递归的执行顺序画出一个树型结构，它称之为递归状态的递归树（或者称为“状态树”）。

下面的题目为求斐波那契数列的第 n 项：

斐波那契数列的项为 0, 1, 1, 2, 3, 5, ….，公式为 F(n) = F(n-1) + F(n-2)，在面试的时候，经常会有人写出下面的解法：

int fib(int n) {
    if (n < 2) return n;
    return fib(n-1) + fib(n-2);
}

我们来分析一下上面解法的时间复杂度，假设 n 为 6。

等 n 为 6 时，发现不满足 n < 2，此时就会走到 fib(5) + fib(4)，所以在计算 fib(6) 的时候就会因此两个分支。要计算 fib(5) 和 fib(4) 的时候，又会根据上图产生不同的分支。从上面的图可以看出，每多展开一层，运行的节点数量就是上一层的两倍。它每一层的执行次数是按指数级去递增的，因此到最后一层的时候，节点数大概是 数量级。从这些我们可以得出斐波那契数列的执行次数是指数级的。

另外从上面的图我们可以看到有重复的节点。 我们可以看到 f(3)、f(2)、f(1) 这些节点被重复计算了很多次，这就导致了求 fib(6) 的时候 这个复杂度。因此在面试的过程中，不要选择使用递归的方式去计算斐波那契数列的第 n 项。我们可以选择加一个缓存将中间的计算结果保存下来。

Master Theorem

主定理是用来解决所有递归函数计算时间复杂度的问题，以下四种情形是在面试和日常工程中会用得到的：

时间复杂度曲线

参考资料

• 算法训练营第二课——时间复杂度与空间复杂度分析