【学习笔记 一】: 算法时间复杂度

先看一个例子，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 取代运行时间肿的所有加法常数。
2. 在修改后的运行次数函数中，只保留最高阶项。
3. 如果高阶项存在且系数不为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)