Skip to main content

算法复杂度

  • 时间复杂度
  • 空间复杂度

时间复杂度​

常用的时间复杂度所耗费的时间由快到慢依次是

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

随着数据量或者 n 的增大，时间复杂度也随之增加，也就是执行时间的增加，会越来越慢，越来越卡

O(1)​

一般情况下，只要算法里没有循环和递归，就算有上万行代码，时间复杂度也是 O(1)，因为它的执行次数不会随着任何一个变量的增大而变长，比如下面这样

function foo(){
    let n = 1
    let b = n * 100
    if(b === 100){
        console.log("开始吃糖")
    }
    console.log("我吃了1颗糖")
    console.log("我吃了2颗糖")
    ......
    console.log("我吃了10000颗糖")
}

O(n)​

只有一层循环或者递归等，时间复杂度就是 O(n)，比如下面这样

function foo1(n){
    for(let i=0;i<n,i++){
        console.log("我吃了一颗糖")
    }
}
function foo2(n)
    while( --n > 0 ){
        console.log("我吃了一颗糖")
    }
function foo3(n) {
    console.log("我吃了一颗糖")
    --n > 0 && foo3(n)
}

O(n²)​

比如嵌套循环，如下面这样的，里层循环执行 n 次，外层循环也执行 n 次，总执行次数就是 n x n，时间复杂度就是 n 的平方，也就是 O(n²)。假设 n 是 10，那么里面的就会打印 10 x 10 = 100 次

function foo1(n) {
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
          console.log("我吃了一颗糖")
        }
    }
}

还有这样的，总执行次数为 n + n²，上面说了，如果是多项式，取最高次项，所以这个时间复杂度也是 O(n²)

function foo2(n){
    for( let k = 0; k < n; k++){
        console.log("我吃了一颗糖")
    }
    for( let i = 0; i < n; i++){
        for( let j = 0; j < n; j++){
            console.log("我吃了一颗糖")
        }
    }
}

//或者下面这样，以运行时间最长的，作为时间复杂度的依据，所以下面的时间复杂度就是 O(n²)
function foo3(n){
    if( n > 100){
        for( let k = 0; k < n; k++){
            console.log("我吃了一颗糖")
        }
    }else{
        for( let i = 0; i < n; i++){
            for( let j = 0; j < n; j++){
                console.log("我吃了一颗糖")
            }
        }
    }
}

O(logn)​

举个栗子，这里有一包糖,这包糖里有 16 颗，沐华每天吃这一包糖的一半，请问多少天吃完？

意思就是 16 不断除以 2，除几次之后等于 1？用代码表示

function foo1(n) {
    let day = 0 // 天数
    while(n > 1){
        n = n/2
        day ++
    }
    return day
}
console.log(foo1(16)); //4

循环次数的影响主要来源于 n/2 ，这个时间复杂度就是 O(logn) ，这个复杂度是怎么来的呢，别着急，继续看 再比如下面这样

function foo2(n){
    for(let i = 0; i < n; i *= 2){
        console.log("一天")
    }
}
foo2( 16 )

复制代码 里面的打印执行了 4 次，循环次数主要影响来源于 i \*= 2 ，这个时间复杂度也是 O(logn)

理解一下规律

  • 真数：就是真数，这道题里就是 16
  • 底数：就是值变化的规律，比如每次循环都是 i\*=2，这个乘以 2 就是规律。比如 1,2,3,4,5...这样的值的话，底就是 1，每个数变化的规律是+1 嘛
  • 对数：在这道题里可以理解成 x2 乘了多少次，这个次数

仔细观察规律就会发现这道题里底数是 2，而我们要求的天数就是这个对数 4，在对数里有一个表达公式

ab = n   读作以 a 为底,b 的对数=n，在这道题里我们知道 a 和 n 的值，也就是   2b = 16 然后求 b

把这个公式转换一下的写法如下

logan = b    在这道题里就是   log216 = ?   答案就是 4

公式是固定的，这个 16 不是固定的，是我们传进去的 n，所以可以理解为这道题就是求 log2n = ? 用时间复杂度表示就是 O(log2n)，由于时间复杂度需要去掉常数和系数，而 log 的底数跟系数是一样的，所以也需要去掉，所以最后这个正确的时间复杂度就是 O(logn)

空间复杂度​

空间复杂度就是算法需要多少内存，占用了多少空间

常用的空间复杂度有:

O(1)<O(n)<O(n²)

O(1)​

只要不会因为算法里的执行，导致额外的空间增长，就算是一万行，空间复杂度也是 O(1)，比如下面这样，时间复杂度也是 O(1)

function foo(){
    let n = 1
    let b = n * 100
    if(b === 100){
        console.log("开始吃糖")
    }
    console.log("我吃了1颗糖")
    console.log("我吃了2颗糖")
    ......
    console.log("我吃了10000颗糖")
}

O(n)​

比如下面这样，n 的数值越大，算法需要分配的空间就需要越多，来存储数组里的值，所以它的空间复杂度就是 O(n)，时间复杂度也是 O(n)

function foo(n){
    let arr = []
    for( let i = 1; i < n; i++ ) {
        arr[i] = i
    }
}

O(n²)​

O(n²) 这种空间复杂度一般出现在比如二维数组，或是矩阵的情况下

不用说，你肯定明白是啥情况啦

就是遍历生成类似这样格式的

let arr = [
    [1,2,3,4,5],
    [1,2,3,4,5],
    [1,2,3,4,5]
]

参考​