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

时间复杂度

时间复杂度是描述算法运行的时间。我们把算法需要运算的次数用输入大小为
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)
直接上代码
1
const a = 1;
2
console.log(a);
Copied!
1
const a = 1;
2
console.log(a, 1);
3
console.log(a, 2);
4
console.log(a, 2);
Copied!
O(1)\mathcal{O}(1)
表示常数级别的复杂度,不管你是
O()\mathcal{O}(几)
,统一给你计作
O(1)\mathcal{O}(1)
  • O(n)\mathcal{O}(n)
    复杂度
1
for (let i = 0; i < n; i++) {
2
// do something
3
}
Copied!
上面这段代码,写了一个 for 循环,从 0 到
nn
,不管
nn
是多少,都要循环
nn
次,而且只循环
nn
次,所以得到复杂度为
O(n)\mathcal{O}(n)
  • O(n2)\mathcal{O}(n^2)
    复杂度
1
for (let i = 0; i < n; i++) {
2
for (let j = 0; j < n; i++) {
3
// do something
4
}
5
}
Copied!
上面的程序嵌套了两个循环,外层是 0 到
nn
,内层基于每一个不同的
ii
,也要从 0 到
nn
执行,得到复杂度为
O(n2)\mathcal{O}(n^2)
。可以看出,随着
nn
增大,复杂度会成平方级别增加。
  • O(log(n))\mathcal{O}(log (n))
    对数复杂度
1
for (let i = 1; i <= n; i *= 2) {
2
// do something
3
}
Copied!
讲到这里顺便来复习一下高中数学知识,函数
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*)
1
function fibonacci(n) {
2
if (n === 0 || n === 1) {
3
return 1;
4
}
5
return fibonacci(n - 1) + fibonacci(n - 2);
6
}
Copied!
我们很容易写出上面这样一段递归的代码,往往会忽略了时间复杂度是多少,换句话说调用多少次。可以代一个数进去,例如 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)}
1
const a = 1;
2
const b = 2;
3
console.log(a);
4
console.log(b);
Copied!
以上代码,分配的空间不会随着处理数据量的变化而变化,因此得到空间复杂度为
O(1){\mathcal{O}(1)}
  • O(n){\mathcal{O}(n)}
    复杂度
先来看这样一段代码
1
const arr = new Array(n);
2
for (let i = 0; i < n; i++) {
3
// do something
4
}
Copied!
上面这段代码的第一行,申请了长度为
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)}
,等学完后面的章节你会发现,复杂度基本上逃不走,都是上面这个几个。
最近更新 1yr ago