先看一个例子，1 + 2 + 3 + ... + n，进行循环累加
function sum1 (n) {
let sum = 0; /* 执行1次 */
for(let i = 0; i <= n; i ++) { /* 执行n + 1次 */
sum = sum + i; /* 执行n次 */
}
return sum;
}
一共执行 2n + 2次；
若我们换种写法：
function sum2 (n) {
return (1 + n) * n / 2; /* 执行1次 */
}
相比之下，很明显sum2的方法要效率更高一些，当n越来越大，sum1的执行次数会越来越高，sum2永远都执行一次，时间效率的差异也就越来越大。
函数的渐进增长
| 输入n | fn1(n) 2n + 3 | fn1'(n) 2n | fn2(n) 3n + 1 | fn2'(n) 3n |
|---|---|---|---|---|
| n = 1 | 5 | 2 | 4 | 3 |
| n = 2 | 7 | 4 | 7 | 6 |
| n = 3 | 9 | 6 | 10 | 9 |
| n = 10 | 23 | 20 | 31 | 30 |
| n = 100 | 203 | 200 | 301 | 300 |
| n = 1000 | 2003 | 2000 | 3001 | 3000 |
可以看到，当输入参数n > 2后，fn1的执行次数与fn2的执行次数的差距越来越大，fn1明显要优于fn2。
给定两个函数f(n) 与 g(n)，如果存在一个整数N，使得对于所有的 n > N，且f(n)总是比g(n)大，那么我们说f(n)的增长渐进快于g(n);
同时我们可以看见，当输入参数逐渐增大的时候，常数部分对算法执行次数的变化，影响不大，所以我们可以忽略加法常数。
| 输入n | fn3(n) 4n + 5 | fn3'(n) n | fn4(n) 2n * n + 4 | fn4'(n) n * n |
|---|---|---|---|---|
| n = 1 | 9 | 1 | 5 | 1 |
| n = 2 | 13 | 2 | 12 | 6 |
| n = 3 | 17 | 3 | 22 | 9 |
| n = 10 | 45 | 10 | 204 | 30 |
| n = 100 | 405 | 100 | 20004 | 10000 |
| n = 1000 | 4005 | 1000 | 2000004 | 1000000 |
随着n的增大，fn4的增长速度明显快于fn3，且常数的影响也越来越小，fn4以指数形势增长，所以n * n项中与之相乘的常数项对于函数的增长速度影响不大，所以说，可以忽略与最高次项相乘的常数项。并且最高次项的指数越大，该函数的增长速度越快，其算法执行次数就越多且越复杂。
| 输入n | fn3(n) 2n^2 + 4n + 5 | fn3'(n) n^2 | fn4(n) n^3 + 2n^2 + 4 | fn4'(n) n^3 |
|---|---|---|---|---|
| n = 1 | 9 | 1 | 7 | 1 |
| n = 2 | 21 | 4 | 20 | 8 |
| n = 3 | 35 | 9 | 22 | 70 |
| n = 10 | 245 | 100 | 204 | 1204 |
| n = 100 | 20405 | 10000 | 1020004 | 1000000 |
| n = 1000 | 2004005 | 1000000 | 1002000004 | 1000000000 |
当最高次项的次数不一样时，也可以看到当他的次数越大，函数的增长速度越快，所以判断一个算法的效率， 函数中的常数和其他次要项常常可以忽略，更应该关注主项即最高阶项的阶数。
这时候我们可以引进算法时间复杂度的概念
算法时间复杂度
算法语句的执行次数T(n)是关于问题规模n的函数，进而分析Tn(n)随着n的增长并确定T(n)的数量级。算法时间复杂度，也就是算法的时间度量，记做T(n) = O(f(n))。它表示随问题规模的增大，算法执行时间的增长率和f(n)的增长率相同， 其中f(n)是问题规模n的某个函数。
通常记做O();例如上述的fn1为O(n)，sum2为O(1)。
推导算法时间复杂度遵守三个原则：
- 用常数1 取代运行时间肿的所有加法常数。
- 在修改后的运行次数函数中，只保留最高阶项。
- 如果高阶项存在且系数不为1，则去除愚者莪项相乘的系数。
常数阶
如sum2的算法时间复杂度就为常数阶，记做O(1);
线性阶
如sum1的算法时间复杂度就为线性阶，记做O(n);
平方阶
function sum3(n) {
for(let i = 0; i <= n; i++) {
for(let j = 0; j <= n; j++) {
/* 算法时间复杂度为O(1)的逻辑 */
}
}
}
为平方阶，记做O(n^2);
对数阶
function sum4(n) {
let sum = 1;
while(sum < n) {
sum = sum * 2
}
}
我们设置执行次数为x，当前2^x = n; 所以x = log2 n
记做O(log n);
算法时间复杂度从小到大一次是
O(1) < O(log n) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)
