开篇——复杂度

算法复杂度是考评算法执行效率和消耗资源的一个重要指标。在符合算法本身的要求的基础上,编写的程序运行时间越短,运行过程中占用的内存空间越少,意味着这个算法越“好”。

时间复杂度

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

常见的时间复杂度

名称

运行时间T(n)T(n)

时间举例

算法举例

常数

O(1)\mathcal{O}(1)

3

-

线性

O(n)\mathcal{O}(n)

nn

操作数组

平方

O(n2)\mathcal{O}(n^2)

n2n^2

冒泡排序

对数

O(log(n))\mathcal{O}(log(n))

log(n)log(n)

二分搜索

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

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

直接上代码

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

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

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

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

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

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

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

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

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

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

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

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

21>22>23...>2x2 ^1 --> 2^2 --> 2^3 ... -->2^x

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

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

根据换底公式

logcalogab=logcblog_c{a} * log_a{b} = log_c{b}

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

递归的时间复杂度

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

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

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

F(0)=1F(1)=1,F(n)=F(n1)+F(n2)n2,nNF(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 的情况都列举出来。可以看出,虽然代码非常简单,在实际运算的时候会有大量的重复计算。

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

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

空间复杂度

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

常见的空间复杂度

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

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

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

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

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

先来看这样一段代码

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

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

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

时间空间相互转换

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

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

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

总结

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