数据结构和算法本身解决的是“快”和“省”的问题，即如何让代码运行的更快，如何让代码更省储存空间。 所以复杂度分析是整个算法学习的精髓。

大O复杂度表示法

推倒大O阶

算法的执行效率，就是算法代码执行的时间。来估算一下下面代码的执行时间。

function sum(n) {
 let total = 0;
 for (let i=0;i < n;i++) {
 total = total + i
 }
 return total;
}

假设每行代码执行的时间都一样，都是unit_time。

第 2 行代码需要 1 个unit_time 的执行时间，第 3、4 行都运行了 n 遍，所以需要 2n*unit_time 的执行时间，所以这段代码总的执行时间就是 (2n+1)*unit_time。

可以看出，代码的执行时间T(n) 与每行代码的执行次数成正比

再来推导下面代码的运行时间：

function sum(n) {
 let total = 0;
 for (let i=1;i<=n;i++) {
 for (let j=1;j<=n;j++) {
 total = total + i * j
 }
 }
 return total
}

同样第2行需要 1个 unit_time 的执行时间，第3行代码循环执行了n遍，需要n * unit_time的执行时间，第4、5行执行了n2 遍，所以需要(2n2+n+1)*unit_time 的执行时间。

尽管我们不知道unit_time的具体值，但通过两段代码的执行时间推导过程，我们得到一个非常重要的规律，那就是，所有代码的执行时间T(n) 与每行代码的执行次数n成正比。

T(n) = O(f(n))

T(n) 代表代码执行的时间，n表示数据规模的大小；f(n)表示每行代码执行的次数总和。公式中的O，表示代码的执行时间T(n) 与f(n) 表达式成正比。

大O时间复杂度实际上并不具体表示代码真正的执行时间，而是表示***代码执行时间随数据规模增加变化的趋势***，所以，也叫做渐进时间复杂度。

当n很大时，公式中的低阶、常量、系数三部分并不左右增长的趋势，所以可以忽略。我们只需要记录一个最大量级就可以了，所以上面两段代码就可以计作：T(n) = O(n) 和 T(n) = O(n2)。

时间复杂度分析方法

• 只关注循环次数最多的一段代码
• 加法法则：总复杂度等于量级最大的那段代码的复杂度
• 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

常见的时间复杂度分析

常数阶 O(1)

O(1)只是常量级时间复杂度的一种表示方法，并不是指只执行了一行代码，比如下面这段代码，即使有3行，他的时间复杂度也是O(1),而不是O(3)。

let i = 2;
let j = 5;
let sun = i + j;

一般情况下，只要算法中不存在循环语句、递归语句，即便有成千上万行代码，其时间复杂度也是O(1)。

线性阶 O(n)

下面这段代码的时间复杂度为O(n)，因为循环体中的代码需要执行n次。

let sum = 0;
for (let i=0;i<n;i++){
 sum = sum +i
}

我们要分析算法的复杂度，关键就是要分析循环结构的运行情况。上面代码因为循环体中代码需要执行n次，所以时间复杂度为O(n)。

对数阶 O(logn) O(nlogn)

对数阶时间复杂度非常常见。

let i = 1;
while (i <= n) {
 i = i * 2
}

从上面代码中可用看出，遍历从1开始，每循环一次就乘以2，当i大于n时循环结束。由于2的x次方等于n，x = log2n，这个循环的时间复杂度就是O(log2n)。不管是以2为底，还是以3为底，我们都可以把所有对数阶的时间复杂度计作：O(logn)。

平方阶 O(n2)

for (let i=0;i<n;i++) {
 for (let j=o;j<n;j++) {
 /*时间复杂度为O(1)的程序步骤*/
 }
}

根据循环的时间复杂度等于循环体的复杂度乘以该循环运行的次数。所以上面代码的时间复杂度为O(n2)。

最优算法

一般情况下，随着n的增大，T(n) 增长最慢的算法为最优算法。

最坏情况

我们查找一个有n个随机数字数组中的某个数字，最好的情况是数组的第一个数字就是，那么算法的时间复杂度为O(1)，但也可能这个数字在最后一位，那么算法的时间复杂度就是O(n)，这就是最坏情况了。

最坏情况运行时间是一种保证，那就是运行时间不会再坏了。通常除非特别指定，我们提到的运行时间都是最坏情况的运行时间。

链接：https://juejin.im/post/5c90844ef265da610d0cbd16

作者：thWinterSun