算法复杂度

算法复杂度

怎么理解算法呢？

简单说就是，同一个功能

  • 别人写的代码跑起来占内存100M,耗时100毫秒
  • 你写的代码跑起来占用内存500M,耗时1000毫秒，甚至更多

所以

衡量代码好坏有两个非常重要的标准: 运行时间(时间复杂度)和占用空间(空间复杂度)

时间复杂度

举个例子

1
2
3
4
5
function fn1(){
    console.log("我吃了一颗糖")
    console.log("我又吃了一颗糖")
    return "再吃一颗糖"
}

调用这个函数，里面总执行次数就是3次

下面这个例子

1
2
3
4
5
6
function foo2(n){
    for( let i = 0; i < n; i++){
        console.log("我吃了一颗糖")
    }
    return "一颗糖"
}

这个函数总执行次数会根据我们传进去的值不一样，执行次数也不一样，大概次数如下

1
2
3
4
5
let i = 0     : 执行 `1` 次
i < n         : 执行 `n+1` 次
i++           : 执行 `n` 次
console.log   : 执行 `n` 次
return        : 执行 `1` 次

这个函数的总执行就是 3n + 3 次

可是我们开发不可能都这样去数，所以根据代码执行时间的推导过程就又一个规律，也就是所有代码执行时间 T(n)和代码的执行次数f(n)是成正比的，而这个规律有一个公式

T(n) = O(f(n))

1
2
3
4
n是输入数据的大小或者输入数据的数量
T(n)表示一段代码的总执行时间
f(n)表示一段代码的总执行次数
O 表示代码的执行时间 T(n) 和 执行次数 f(n) 成正比

算法复杂度的 O() 就是这么来的，我们平时表示算法复杂度主要就是 O(), 读作大欧表示法

上面的两个例子

  • 第一个函数执行了3次，复杂度就是 O(3)
  • 第二个函数执行了3n+3次，复杂大就是O(3n+3)

这样就会很麻烦，因为如果函数逻辑一样，只是执行次数差了几次，想O(3)和O(4),有什么差别呢？还要写成两种就多此一举了，所以复杂度李有统一的简化表示法，这个执行时间简化的估算值就是我们最终的 时间复杂度

简化过程如下

  • 如果只是常熟直接估算为1， O(3)的时间复杂度就是O(1)，不是说只执行了1次，而是对常量级时间复杂度的一种表示法。一般情况下，只要算法里没有循环和递归，就算有上万行代码，时间复杂度也是O(1)
  • O(3n+4)里面常数3对于总执行次数几乎没有影响，直接忽略不计，系数3影响也不大,因为3n和n都是一个量级的，所以作为系数的常数3也估算为1或者可以理解为去掉系数，所以O(3n+3)的时间复杂度为 O(n)
  • 如果是多项式，只需要保留n的最高次项，O(666n³ + 666n² + n)，这个复杂度里面的最高次项是n得3次方。因为随着n的增大，后面的项的增值远远不及n的最高次项大，所以低于这个次项的直接忽略不计，常数也忽略不计，简化后的 时间复杂度为O(n³)

常用时间复杂度

O(1)

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

1
2
3
4
5
6
7
8
9
10
11
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),举个例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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 n , 时间复杂度就是 n的平方，也就是O(n²)。假设n是10，那么里面就会打印10 10 = 100 次

1
2
3
4
5
6
7
function foo1(n){
    for( let i = 0; i < n; i++){
        for( let j = 0; j < n; j++){
            console.log("我吃了一颗糖")
        }
    }
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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(1)
        }
    }
}

//或者下面这样，以运行时间最长的，作为时间复杂度的依据，所以下面的时间复杂度就是 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？用代码表示

1
2
3
4
5
6
7
8
9
function fool1(n){
    let day = 0
    while(n > 1){
        n = n / 2
        day ++ 
    }
    return day
}

循环次数的影响主要来源于 n/2 , 这个时间复杂度就是 O(logn),

再比如下面这样

1
2
3
4
5
6
function foo2(n){
    for(let i = 1; i < n; i *= 2){
        console.log("一天")
    }
}
foo2( 16 )

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

这个O(logn)是怎么来的，看下图

没有理解的话再看一下，理解一下规律

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

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

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

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

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

公式是固定的，这个16不是固定的，是我们传进去的 n，所以可以理解为这道题就是求 log2n = ?

用时间复杂度表示就是 O(log2n)，由于时间复杂度需要去掉常数和系数，而log的底数跟系数是一样的，所以也需要去掉，所以最后这个正确的时间复杂度就是 O(logn)

其他还有一些时间复杂度，我由快到慢排列了一下，如下表顺序

复杂度 名称
O(1) 常数复杂度
O(logn) 对数复杂度
O(n) 线性时间复杂度
O(nlogn) 线性对数复杂度
O(n²) 平方
O(n³) 立方
O(2^n) 指数，一点数据就卡
O(n!) 阶乘，更慢

这些时间复杂度有什么区别呢，看张图

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

空间复杂度

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

常用的空间复杂度有 O(1),O(n),O(n^2)

O(1)

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

1
2
3
4
5
6
7
8
9
10
11
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)

1
2
3
4
5
6
function foo(n){
    let arr = []
    for( let i = 1; i < n; i++ ) {
        arr[i] = i
    }
}

O(n²)

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

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

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