算法中的复杂度分析

# 什么是算法

算法就是对数据结构的操作。

# 为什么需要时间复杂度分析

基于事后统计法，我们可以通过统计、监控来看我们算法性能的执行时间和内存占用，既然这么方便，那为什么我们还要做复杂度分析？
我们来看一下事后统计法存在一定的局限性：

1. 测试结果依赖测试环境 同样的代码在不同的机器上运行效率肯定会不一样。
2. 测试数据量的不同会有偏差 比如排序算法中需要排序个数50个和5000个需要占用的时间和内存会不一样。

# 复杂度表示法

先来看一段程序:

const cal = (n) => {
   let sum = 0, i = 1;
   for (; i <= n; ++i) {
     sum = sum + i;
   }
   return sum;
 }

假设每个语句的执行时间为 unitTime ，那么上面这段程序的总执行时间 T(n) 是多少？
先看第2行代码的声明语句，执行时间为 1 unitTime, 第3，4行都执行了 n unitTime，所以算一下一共的 T(n) = (1+n+n) unitTime。 可以总结一下，代码的执行总时间 T(n) 总是和代码的执行次数成正比，我们把这个规律总结成一个公式，即大 O 表示法:
T(n) = O(f(n)) 上面这个例子中 T(n) = O(1+2n)，这就是大 O 时间复杂度的表示方式。

# 时间复杂度分析

复杂度的分析，我们一般会忽略掉公式中的常量、低阶、系数，只记录最大阶的量级。

以下是分析时间复杂度的三个方法

# 1. 只关注循环执行次数最多的一次

以上面的例子来说：

const cal = (n) => {
   let sum = 0;
   for (let i = 1; i <= n; i++) {
     sum = sum + i;
   }
   return sum;
 }

第二行的代码执行时间是常量级的与循环次数 n 无关，所以可以忽略不计，第3，4行两行代码都执行了 n 次，即这两行代码执行次数都是 n 的量级，所以总的时间复杂度是 O(n)

# 2. 加法法则

总复杂度 === 量级最大的代码的复杂度

先看一段代码

const cal = (n) => {
   let sum = 0;
   for (let p = 1; p < 100; p++) {
     sum = sum + p;
   }
 
   let sum2 = 0;
   for (let q = 1; q < n; q++) {
     sum2 = sum2 + q;
   }
 
   let sum3 = 0;
   for (let i = 1; i <= n; i++) {
     j = 1; 
     for (let j = 1; j <= n; j++) {
       sum3 = sum3 +  i * j;
     }
   }
 
   return sum + sum2 + sum3;
 }

简单分析一下，这段代码分别求sum sum2 sum3 的值，第一段执行的时间为100 unitTime，即常量级执行次数，与 n 无关。第二段代码执行的时间为 n unitTime, 第三段 的执行时间为 n*n unitTime，所以三段的代码的时间复杂度分别为：

1. T1(n) = O(f(100))
2. T2(n) = O(g(n))
3. T3(n) = O(k(n*n))

总的 T(n) = T1(n) + T2(n) + T3(n)，结合上面说的，总复杂度 = 量级最大的代码的复杂度，即 T(n) = max(T1(n), T2(n), T3(n))，所以上面代码的时间复杂度为 O(n*n)

# 3. 乘法法则

嵌套代码的复杂度 === 嵌套内外代码复杂度的乘积

根据加法法则，我们可以推断出乘法法则下的时间复杂度，即假设

1. T1(n) = O(f(n))
2. T2(n) = O(g(n))

那么 TO === T1(n) * T2(n) === O(f(n)) * O(g(n)) 举个🌰：

const cal = (n) => {
    let sum = 0
    for (let i = 1; i < n; i++) {
        sum = sum + f(i)
    }
    
    const f = (n) => {
        let sum = 0
        for (let i = 1; i < n; i++) {
            sum = sum + i
        }
    }
}

其中第一段 for 循环中 排除 f 函数的执行，第一段代码的时间复杂度为 O(n), 但是 f 函数的时间复杂度又是O(n)，所以整个 cal 函数的时间复杂度就是 T(n) = O(n) * O(n) 即 T(n) = O(n*n) 以上是三种常见的复杂度分析手段。

# 常见的复杂度量级

可分为两大类

• 多项式量级
  1. 常量阶 O(1)
  2. 对数阶 O(logn)
  3. 线性阶 O(n)
  4. 线性对数阶 O(nlogn)
  5. 平方阶 O(n*n) O(n^2) O(n^3) O(n^n)
• 非多项式量级
  1. 指数阶 O(2^n) 即2的 n 次方
  2. 阶乘阶 O(n!) 即 5! === 5*4*3*2*1 其中非多项式量级算法的效率比较低，当 n 的量级越来越大的时候，非多项式量级算法花费的时间会越来越多。所以，非多项式量级的算法是非常低效的算法。

# 常见的多项式量级算法

# 1. O(1)

const a = 1
const b = 2
const sum = a + b

上面的代码，就算是有3行语句，时间复杂度也是 O(1)，可以说，代码执行时间不随着 n 的增大而增大的话，这样的代码执行的时间复杂度都是 O(1)。一般情况下， 程序或者算法中不存在循环、递归等语句，其时间复杂度都是常量级 O(1)

# 2. 对数阶复杂度 O(logn) O(nlogn)

对数阶时间复杂度是比较难分析的一种，先看代码：

let i = 1
while (i < n) {
    i = i * 2
}

根据上面的复杂度分析法，我们只要分析循环执行最多的代码就好，看第3行，当 i > n 的时候，循环结束。我们可以用等比数列的方式，把代码的执行次数列出来，因为 i 每次要 *2，所以

// 等比数列
2^0, 2^1, 2^2, 2^3 ... 2^k, 2^x = n

根据数学知识，求的 x = log2^n 所以这端代码的时间复杂度就是 O(log2^n)。 稍微改下代码：

let i = 1
while (i < n) {
    i = i * 3
}

显而易见这段代码的时间复杂度就是 O(log3^n) 简单总结一下，不管以2为底，还是以3为底，还是以10为底，我们可以把这种对数阶的时间复杂度统称为 O(logn)

# 3. O(m+n), O(m*n)

以数据规模局决定的时间复杂度

const cal = (m, n) => {
    let sum = 0
    for (let i = 1; i < m; i++) {
        sum = sum + i
    }
    let sum2 = 0
    for (let j = 1; j < n; j++) {
      sum2 = sum2+ i
    }
    return sum + sum2
}

从上面的代码中可以看出 m,n 都是数据规模，我们无法确定 m,n的规模谁大谁小，所以上面代码的时间复杂度就是 O(m+n)。 再来看另外一段代码:

const cal = (m, n) => {
    let sum = 0
    for (let i = 1; i < m; i++) {
        sum = sum + i
        let sum2 = 0
        for (let j = 1; j < n; j++) {
          sum2 = sum2+ i
        }
    }
    return sum + sum2
}

当代码中有循环嵌套的时候，我们就可以使用乘法运算了，所以上面代码的时间复杂度就是 O(m*n)

# 空间复杂度分析

时间复杂度是代码执行时间与数据规模之间的增长关系，空间复杂度就是存储空间与数据规模之间的增长关系

先看一段代码：

const print = (n) => {
    const a = []
    for (let i = 0; i < n; i++) {
        a[i] = i * i
    }
    for (let i = n-1; i >= 0; i--) {
        console.log(a[i])
    }
}

我们先看一下第2行高亮代码，我们声明了一个空数组，这个空数组在执行到第2行的时候，与数据规模 n，没有关系，但是当执行到第3行的 for 循环的时候， 内存空间就与 n 有关系了，所以这段代码的的空间复杂度就是 O(n)。 空间复杂度比较简单，常见的就是 O(1),O(n), O(n^2)，诸如时间复杂度的对数阶时间复杂度，在空间复杂度中都是用不到的。