7.md

时间复杂度和空间复杂度

如何评价一个算法的好坏呢？我们通常通过两个维度来表示：

• 时间维度

是指执行当前算法所消耗的时间，通常用 时间复杂度 来描述。

• 空间维度

是指执行当前算法需要占用多少内存空间，通常用 空间复杂度 来描述。

时间复杂度

在计算时间复杂度我们通常采用大O表示法, 即 T(n) = O( f(n) ), 其中f(n) 表示每行代码执行次数之和，而 O 表示正比例关系，这个公式的全称是：算法的渐进时间复杂度。

也可以理解为，随着数据规模的增长，所需要的运行时间。

常见的时间复杂度有：

• O(1):Constant Complexity 常数复杂度
• O(log n):Logarithmic Complexity 对数复杂度
• O(n):Linear Complexity 线性时间复杂度
• O(n^2): N square Complexity 平⽅
• O(n^3): N square Complexity ⽴⽅
• O(2^n): Exponential Growth 指数
• O(n!): Factorial 阶乘

常用的时间复杂度按照耗费的时间从小到大依次是：

O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³)<O(2ⁿ)<O(n!)

如何计算时间复杂度

时间复杂度就是时间频度去掉常数项、去掉低阶项、去掉最高次阶的系数，只保留最高次阶

第一步： 去掉常数项

T(n) = 5n^2 + 10n + 7 去掉常数项为 T(n) = 5n^2 + 10n

第二步： 去掉低阶项

T(n) = 5n^2 + 10n 去掉常数项为 T(n) = 5n^2

第三步：去掉最高次阶的系数

T(n) = 5n^2 去掉最高次阶的系数为 T(n) = n^2

比较不错的视频

常数阶O(1)

const a = 100; // 1
const b = 200; // 1
const fn = () => return a; // 1

语句所需要的时间f(n) = 1 + 1 + 1 = 3 时间复杂度：T(n) = O(f(n)) = O(3) = O(1)

对数阶O(logN)

for(int i =1; i < n; i = i * 2) {
  console.log('i', i)
}

线性阶O(n)

for ( int i = 0; i < n; i++) {
    // do .....
}

线性对数阶O(nlogN)

 function fn( n ){
    let s = 1;
    for (int i = 0; i < n; i++) {
        while (i <= n) {
            i = i * 2;
        }
    }
    return s;
}

平方阶O(n²)

for (int i = 0; i < n; i++) {
    for (int j = i; j < n; j++) {
        // do .....
    }
}

立方阶O(n³)

for (let i = 0; i < n; i++) {
    for (let j = i; j < n; j++) {
       for(let k = 0; k < n; k++){
           // do ....
       }
    }
}

指数(k^n)

指数级的时间复杂度k, 可以是2等。 指数的例子我们以斐波那契额数列为例子。

function fibonacci(n){
    if(n <= 2) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

以 6 的斐波那契额数列为例子，以递归(不带记忆化的递归)进行求解，递归状态树：

可以分析出:

第一层1个节点 2^0。 第二层 2个节点2^1。 第三层 4个节点2^2。 ...

随着数据规模的增大，时间复杂度指数级是2^n。

阶乘(n!)

一个正整数的阶乘是所有小于及等于该数的正整数的积，并且 0 的阶乘为1。自然数n的阶乘写作n!。

即

n!=1×2×3×...×(n-1)×n

function factorial (num) { 
    if (num < 0) { 
        return -1; 
    } else if (num === 0 || num === 1) { 
        return 1; 
    } else { 
        return (num * factorial(num - 1)); 
    } 
};

空间复杂度

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。