开篇——复杂度

时间复杂度
时间复杂度是描述算法运行的时间。我们把算法需要运算的次数用输入大小为 nnn
 的函数来表示，计作 T(n)T(n)T(n)
。时间复杂度通常用O(n)\mathcal{O}(n)O(n)
来表示，公式为T(n)=O(f(n))T(n) = \mathcal{O}(f(n))T(n)=O(f(n))
，其中f(n)f(n)f(n)
表示每行代码的执行次数之和，注意是执行次数。
常见的时间复杂度
名称
运行时间T(n)T(n)T(n)
​
时间举例
算法举例
常数
​O(1)\mathcal{O}(1)O(1)
​
3
-
线性
​O(n)\mathcal{O}(n)O(n)
​
​nnn
​
操作数组
平方
​O(n2)\mathcal{O}(n^2)O(n2)
​
​n2n^2n2
​
冒泡排序
对数
​O(log(n))\mathcal{O}(log(n))O(log(n))
​
​log(n)log(n)log(n)
​
二分搜索
​O(1)\mathcal{O}(1)O(1)
 复杂度
算法执行所需要的时间不随着某个变量nnn
的大小而变化，即此算法时间复杂度为一个常量，可表示为 O(1)\mathcal{O}(1)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(1)
表示常数级别的复杂度，不管你是O(几)\mathcal{O}(几)O(几)
，统一给你计作 O(1)\mathcal{O}(1)O(1)
​
​O(n)\mathcal{O}(n)O(n)
 复杂度
1
for (let i = 0; i < n; i++) {
2
    // do something
3
}
Copied!
上面这段代码，写了一个 for 循环，从 0 到 nnn
，不管 nnn
 是多少，都要循环 nnn
 次，而且只循环 nnn
 次，所以得到复杂度为 O(n)\mathcal{O}(n)O(n)
​
​O(n2)\mathcal{O}(n^2)O(n2)
 复杂度
1
for (let i = 0; i < n; i++) {
2
    for (let j = 0; j < n; i++) {
3
        // do something
4
    }
5
}
Copied!
上面的程序嵌套了两个循环，外层是 0 到 nnn
，内层基于每一个不同的 iii
，也要从 0 到 nnn
 执行，得到复杂度为 O(n2)\mathcal{O}(n^2)O(n2)
。可以看出，随着 nnn
 增大，复杂度会成平方级别增加。
​O(log(n))\mathcal{O}(log (n))O(log(n))
 对数复杂度
1
for (let i = 1; i <= n; i *= 2) {
2
    // do something
3
}
Copied!
讲到这里顺便来复习一下高中数学知识，函数y=logaxy = log_a{x}y=loga​x
叫做对数函数，aaa
就是对数函数的底数。
对数复杂度是比较常见的一种复杂度，也是比较难分析的一种复杂度。观察上面的代码，iii
 从 1 开始，每循环一次就乘以 2，直到 iii
 大于 nnn
 时结束循环。
​21−−>22−−>23...−−>2x2 ^1 --> 2^2 --> 2^3 ... -->2^x21−−>22−−>23...−−>2x
​
观察上面列出 i 的取值发现，是一个等比数列，要知道循环了多少次，求出 xxx
 的值即可。由 2x=n2^x = n2x=n
得到，x=log2nx = log_2{n}x=log2​n
，所以这段代码的时间复杂度为log2nlog_2{n}log2​n
。
如果把上面的 i *= 2 改为 i *= 3，那么这段代码的时间复杂度就是 log3nlog_3{n}log3​n
。
根据换底公式：
​logca∗logab=logcblog_c{a} * log_a{b} = log_c{b}logc​a∗loga​b=logc​b
 
因此 log3n=log32∗log2nlog_3{n} = log_3{2} * log_2{n}log3​n=log3​2∗log2​n
 ，而 log32log_3{2}log3​2
 是一个常量，得到 O(log3(n))=O(log2(n))\mathcal{O}(log_3(n)) = \mathcal{O}(log_2(n))O(log3​(n))=O(log2​(n))
。所以，在对数时间复杂度的表示中，我们忽略对数的“底”，我不管你底数是多少，统一计作O(log(n))\mathcal{O}(log (n))O(log(n))
。
递归的时间复杂度
在面试的时候，可能会写到一些递归的程序，那么递归的时间复杂度如何考虑？
递归算法中，每个递归函数的的时间复杂度为O(s)O(s)O(s)
，递归的调用次数为 nnn
，则该递归算法的时间复杂度为 O(n)=n∗O(s)O(n) = n * O(s)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∗）F(0)=1，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2,n ∈ N*）F(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 的情况都列举出来。可以看出，虽然代码非常简单，在实际运算的时候会有大量的重复计算。
在 nnn
 层的完全二叉树中，节点的总数为 2n−12^n -12n−1
，所以得到 F(n)F(n)F(n)
 中递归数目的上限为 2n−12^n -12n−1
。因此我们可以毛估出 F(n)F(n)F(n)
 的时间复杂度为 O(2n){\mathcal{O}(2^n)}O(2n)
。
时间复杂度为 O(2n)\mathcal{O}(2^n)O(2n)
，指数级的时间复杂度，显然不是最优的解法，让计算机傻算了很多次，所以在面试时要稍微留意，如果写出这样的代码，可能会让你的面试官不太满意。
空间复杂度
空间复杂度是对算法运行过程中临时占用空间大小的度量，一个算法所需的存储空间用f(n)f(n)f(n)
表示，可得出S(n)=O(f(n))S(n)=\mathcal{O}(f(n))S(n)=O(f(n))
，其中 nnn
 为问题的规模，S(n)S(n)S(n)
表示空间复杂度。通常用 S(n)S(n)S(n)
 来定义。
常见的空间复杂度
​O(1){\mathcal{O}(1)}O(1)
 复杂度
算法执行所需要的临时空间不随着某个变量 nnn
 的大小而变化，即此算法空间复杂度为一个常量，可表示为 O(1){\mathcal{O}(1)}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(1)
​
​O(n){\mathcal{O}(n)}O(n)
 复杂度
先来看这样一段代码
1
const arr = new Array(n);
2
for (let i = 0; i < n; i++) {
3
    // do something
4
}
Copied!
上面这段代码的第一行，申请了长度为 nnn
 的数组空间，下面的 for 循环中没有分配新的空间，可以得出这段代码的时间复杂度为 O(n){\mathcal{O}(n)}O(n)
。
对数阶的空间复杂度非常少见，而且空间复杂度的分析相对与时间复杂度分析简单很多，这部分不再阐述。
时间空间相互转换
对于一个算法来说，它的时间复杂度和空间复杂度往往是相互影响的。
那我们熟悉的 Chrome 来说，流畅性方面比其他厂商好了多人，但是占用的内存空间略大。
当追求一个较好的时间复杂度时，可能需要消耗更多的储存空间。 反之，如果追求较好的空间复杂度，算法执行的时间可能就会变长。
总结
常见的复杂度不多，从低到高排列就这么几个：O(1)O(1)O(1)
、O(log(n)){O(log(n))}O(log(n))
、O(n){O(n)}O(n)
、O(n2){O(n^2)}O(n2)
，等学完后面的章节你会发现，复杂度基本上逃不走，都是上面这个几个。
以前
学习指南
下一个
字符串
最近更新 1yr ago
复制链接
内容