时间复杂度是描述算法运行的时间。我们把算法需要运算的次数用输入大小为 的函数来表示,计作 。时间复杂度通常用来表示,公式为,其中表示每行代码的执行次数之和,注意是执行次数。
名称 | 运行时间 | 时间举例 | 算法举例 |
常数 | | 3 | - |
线性 | | | 操作数组 |
平方 | | | 冒泡排序 |
对数 | | | 二分搜索 |
复杂度
算法执行所需要的时间不随着某个变量的大小而变化,即此算法时间复杂度为一个常量,可表示为
直接上代码
const a = 1;console.log(a);
const a = 1;console.log(a, 1);console.log(a, 2);console.log(a, 2);
表示常数级别的复杂度,不管你是,统一给你计作
复杂度
for (let i = 0; i < n; i++) {// do something}
上面这段代码,写了一个 for 循环,从 0 到 ,不管 是多少,都要循环 次,而且只循环 次,所以得到复杂度为
复杂度
for (let i = 0; i < n; i++) {for (let j = 0; j < n; i++) {// do something}}
上面的程序嵌套了两个循环,外层是 0 到 ,内层基于每一个不同的 ,也要从 0 到 执行,得到复杂度为 。可以看出,随着 增大,复杂度会成平方级别增加。
对数复杂度
for (let i = 1; i <= n; i *= 2) {// do something}
讲到这里顺便来复习一下高中数学知识,函数叫做对数函数,就是对数函数的底数。
对数复杂度是比较常见的一种复杂度,也是比较难分析的一种复杂度。观察上面的代码, 从 1 开始,每循环一次就乘以 2,直到 大于 时结束循环。
观察上面列出 i 的取值发现,是一个等比数列,要知道循环了多少次,求出 的值即可。由 得到,,所以这段代码的时间复杂度为。
如果把上面的 i *= 2
改为 i *= 3
,那么这段代码的时间复杂度就是 。
根据换底公式:
因此 ,而 是一个常量,得到 。所以,在对数时间复杂度的表示中,我们忽略对数的“底”,我不管你底数是多少,统一计作。
在面试的时候,可能会写到一些递归的程序,那么递归的时间复杂度如何考虑?
递归算法中,每个递归函数的的时间复杂度为,递归的调用次数为 ,则该递归算法的时间复杂度为
我们先来看一个经典的问题,斐波那契数列(Fibonacci sequence
):
function fibonacci(n) {if (n === 0 || n === 1) {return 1;}return fibonacci(n - 1) + fibonacci(n - 2);}
我们很容易写出上面这样一段递归的代码,往往会忽略了时间复杂度是多少,换句话说调用多少次。可以代一个数进去,例如 n = 5,完了之后大概就能理解递归的时间复杂度是怎么来的。
上图把 n = 5 的情况都列举出来。可以看出,虽然代码非常简单,在实际运算的时候会有大量的重复计算。
在 层的完全二叉树中,节点的总数为 ,所以得到 中递归数目的上限为 。因此我们可以毛估出 的时间复杂度为 。
时间复杂度为 ,指数级的时间复杂度,显然不是最优的解法,让计算机傻算了很多次,所以在面试时要稍微留意,如果写出这样的代码,可能会让你的面试官不太满意。
空间复杂度是对算法运行过程中临时占用空间大小的度量,一个算法所需的存储空间用表示,可得出,其中 为问题的规模,表示空间复杂度。通常用 来定义。
复杂度
算法执行所需要的临时空间不随着某个变量 的大小而变化,即此算法空间复杂度为一个常量,可表示为
const a = 1;const b = 2;console.log(a);console.log(b);
以上代码,分配的空间不会随着处理数据量的变化而变化,因此得到空间复杂度为
复杂度
先来看这样一段代码
const arr = new Array(n);for (let i = 0; i < n; i++) {// do something}
上面这段代码的第一行,申请了长度为 的数组空间,下面的 for 循环中没有分配新的空间,可以得出这段代码的时间复杂度为 。
对数阶的空间复杂度非常少见,而且空间复杂度的分析相对与时间复杂度分析简单很多,这部分不再阐述。
对于一个算法来说,它的时间复杂度和空间复杂度往往是相互影响的。
那我们熟悉的 Chrome 来说,流畅性方面比其他厂商好了多人,但是占用的内存空间略大。
当追求一个较好的时间复杂度时,可能需要消耗更多的储存空间。 反之,如果追求较好的空间复杂度,算法执行的时间可能就会变长。
常见的复杂度不多,从低到高排列就这么几个:、、、,等学完后面的章节你会发现,复杂度基本上逃不走,都是上面这个几个。