开篇——复杂度

时间复杂度

时间复杂度是描述算法运行的时间。我们把算法需要运算的次数用输入大小为 $n$ 的函数来表示，计作 $T(n)$。时间复杂度通常用$\mathcal{O}(n)$来表示，公式为$T(n) = \mathcal{O}(f(n))$，其中$f(n)$表示每行代码的执行次数之和，注意是执行次数。

常见的时间复杂度

• ​$\mathcal{O}(1)$ 复杂度

算法执行所需要的时间不随着某个变量$n$的大小而变化，即此算法时间复杂度为一个常量，可表示为 $\mathcal{O}(1)$​

直接上代码

const a = 1;
console.log(a);

const a = 1;
console.log(a, 1);
console.log(a, 2);
console.log(a, 2);

​$\mathcal{O}(1)$表示常数级别的复杂度，不管你是$\mathcal{O}(几)$，统一给你计作 $\mathcal{O}(1)$​

• ​$\mathcal{O}(n)$ 复杂度

for (let i = 0; i < n; i++) {
    // do something
}

上面这段代码，写了一个 for 循环，从 0 到 $n$，不管 $n$ 是多少，都要循环 $n$ 次，而且只循环 $n$ 次，所以得到复杂度为 $\mathcal{O}(n)$​

• ​$\mathcal{O}(n^2)$ 复杂度

for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; i++) {
        // do something
    }
}

上面的程序嵌套了两个循环，外层是 0 到 $n$，内层基于每一个不同的 $i$，也要从 0 到 $n$ 执行，得到复杂度为 $\mathcal{O}(n^2)$。可以看出，随着 $n$ 增大，复杂度会成平方级别增加。

• ​$\mathcal{O}(log (n))$ 对数复杂度

for (let i = 1; i <= n; i *= 2) {
    // do something
}

讲到这里顺便来复习一下高中数学知识，函数$y = log_a{x}$叫做对数函数，$a$就是对数函数的底数。

对数复杂度是比较常见的一种复杂度，也是比较难分析的一种复杂度。观察上面的代码，$i$ 从 1 开始，每循环一次就乘以 2，直到 $i$ 大于 $n$ 时结束循环。

​$2 ^1 --> 2^2 --> 2^3 ... -->2^x$​

观察上面列出 i 的取值发现，是一个等比数列，要知道循环了多少次，求出 $x$ 的值即可。由 $2^x = n$得到，$x = log_2{n}$，所以这段代码的时间复杂度为$log_2{n}$。

如果把上面的 i *= 2 改为 i *= 3，那么这段代码的时间复杂度就是 $log_3{n}$。

根据换底公式：

​$log_c{a} * log_a{b} = log_c{b}$

因此 $log_3{n} = log_3{2} * log_2{n}$ ，而 $log_3{2}$ 是一个常量，得到 $\mathcal{O}(log_3(n)) = \mathcal{O}(log_2(n))$。所以，在对数时间复杂度的表示中，我们忽略对数的“底”，我不管你底数是多少，统一计作$\mathcal{O}(log (n))$。

递归的时间复杂度

在面试的时候，可能会写到一些递归的程序，那么递归的时间复杂度如何考虑？

递归算法中，每个递归函数的的时间复杂度为$O(s)$，递归的调用次数为 $n$，则该递归算法的时间复杂度为 $O(n) = n * O(s)$

我们先来看一个经典的问题，斐波那契数列(Fibonacci sequence)：

​$F(0)=1，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2,n ∈ N*）$

function fibonacci(n) {
    if (n === 0 || n === 1) {
        return 1;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

我们很容易写出上面这样一段递归的代码，往往会忽略了时间复杂度是多少，换句话说调用多少次。可以代一个数进去，例如 n = 5，完了之后大概就能理解递归的时间复杂度是怎么来的。

上图把 n = 5 的情况都列举出来。可以看出，虽然代码非常简单，在实际运算的时候会有大量的重复计算。

在 $n$ 层的完全二叉树中，节点的总数为 $2^n -1$，所以得到 $F(n)$ 中递归数目的上限为 $2^n -1$。因此我们可以毛估出 $F(n)$ 的时间复杂度为 ${\mathcal{O}(2^n)}$。

时间复杂度为 $\mathcal{O}(2^n)$，指数级的时间复杂度，显然不是最优的解法，让计算机傻算了很多次，所以在面试时要稍微留意，如果写出这样的代码，可能会让你的面试官不太满意。

空间复杂度

空间复杂度是对算法运行过程中临时占用空间大小的度量，一个算法所需的存储空间用$f(n)$表示，可得出$S(n)=\mathcal{O}(f(n))$，其中 $n$ 为问题的规模，$S(n)$表示空间复杂度。通常用 $S(n)$ 来定义。

常见的空间复杂度

• ​${\mathcal{O}(1)}$ 复杂度

算法执行所需要的临时空间不随着某个变量 $n$ 的大小而变化，即此算法空间复杂度为一个常量，可表示为 ${\mathcal{O}(1)}$​

const a = 1;
const b = 2;
console.log(a);
console.log(b);

以上代码，分配的空间不会随着处理数据量的变化而变化，因此得到空间复杂度为${\mathcal{O}(1)}$​

• ​${\mathcal{O}(n)}$ 复杂度

先来看这样一段代码

const arr = new Array(n);
for (let i = 0; i < n; i++) {
    // do something
}

上面这段代码的第一行，申请了长度为 $n$ 的数组空间，下面的 for 循环中没有分配新的空间，可以得出这段代码的时间复杂度为 ${\mathcal{O}(n)}$。

对数阶的空间复杂度非常少见，而且空间复杂度的分析相对与时间复杂度分析简单很多，这部分不再阐述。

时间空间相互转换

对于一个算法来说，它的时间复杂度和空间复杂度往往是相互影响的。

那我们熟悉的 Chrome 来说，流畅性方面比其他厂商好了多人，但是占用的内存空间略大。

当追求一个较好的时间复杂度时，可能需要消耗更多的储存空间。 反之，如果追求较好的空间复杂度，算法执行的时间可能就会变长。

总结

常见的复杂度不多，从低到高排列就这么几个：$O(1)$、${O(log(n))}$、${O(n)}$、${O(n^2)}$，等学完后面的章节你会发现，复杂度基本上逃不走，都是上面这个几个。