数据结构和算法本身解决的是“快”和“省”的问题，即如何让代码运行的更快，如何让代码更省储存空间。 所以复杂度分析是整个算法学习的精髓。
大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行执行了n² 遍，所以需要(2n²+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(n²)。
时间复杂度分析方法
- 只关注循环次数最多的一段代码
- 加法法则：总复杂度等于量级最大的那段代码的复杂度
- 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
常见的时间复杂度分析
常数阶 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(n²)
for (let i=0;i<n;i++) {
for (let j=o;j<n;j++) {
/*时间复杂度为O(1)的程序步骤*/
}
}
根据循环的时间复杂度等于循环体的复杂度乘以该循环运行的次数。所以上面代码的时间复杂度为O(n²)。
最优算法
一般情况下，随着n的增大，T(n) 增长最慢的算法为最优算法。
最坏情况
我们查找一个有n个随机数字数组中的某个数字，最好的情况是数组的第一个数字就是，那么算法的时间复杂度为O(1)，但也可能这个数字在最后一位，那么算法的时间复杂度就是O(n)，这就是最坏情况了。
最坏情况运行时间是一种保证，那就是运行时间不会再坏了。通常除非特别指定，我们提到的运行时间都是最坏情况的运行时间。
本文摘自极客时间王争老师的 数据结构与算法之美
摘自《大话数据结构》
