为什么算法复杂度分析，是学算法最核心的一步

基本介绍

算法复杂度这个概念，是算法中比较重要的一个核心的点。假设你现在要去分辨一串代码写的好与坏，那么是不是就得需要有一个可以衡量的标准，而算法复杂度的分析，就是一把标准之尺，有了这把尺子，你就能分辨出那些写的糟糕的代码，同时你也知道了要怎样去优化这段代码。

而目前我们常用的分析法，也就是大O表示法

常见复杂度

我们看一下 下面的代码

   function fn(n) {
let m = 0
console.log(m)
for (let i = 0; i <= n; i = ++ ) {

          m += i

          m--

      }

  }

我们假设 一行代码的执行的消耗时间是 1run_time 那么以此推导上面代码执行的时间消耗是(3n + 2)run_time 那么用大O表示法就是O(3n + 2)。

ps：本文中中次的概念对应 每行代码 而不是整个代码片段

大O表示法，并不会具体分析出每行代码执行花费的时间，他是一个粗略的抽象的统计概念，主要是是表示的某段代码的，所消耗的(时间/空间)增长趋势

O表示是 总耗时 和总次数的一个比值，可以简单理解为 每一次代码执行所需要花费的耗时，也就是 总时间/总次数 = 每次执行需要消耗的平均时长。

那么刚刚的O(3n + 2) 其实就是 (3n + 2) * 每次代码需要消耗的平均时长，那么就可以得出一个公式 T(n) = O(代码执行的总次数)

其中 T(n) 表示的是 整段代码执行需要的总耗时

在大O表示法中，常数，低阶，系数，在表示的时候是可以直接忽略统计的的，那么最后实际表示的复杂度就是O(n) 了

我们再来看下面的代码

 function fn(n) {
let aa = 0
let bb = 0

for (let i = 0; i < n; ++i) {

          aa += i

      }

for (let i = 0; i < n; ++i) {
for (let k = 0; k < n; ++i) {

              bb += k

          }

      }


  }

前两行代码 很好看出来 就是个2，第一个for循环的消耗是 2n 第二个for循环 消耗是n的二次方那么实际用大O 表示就是 O(2 + 2n + n²) 最后表示的时候取3块代码中增长趋势最大的也就是O(n²)

O(logn) O(nlogn)

理解了上面分析的内容之后，这两个 O(logn), O(nlogn) 复杂度就很容易去学会了

 function fn(n) {
let m = 0
for (let i = 0; i < n; i *= 2) {

          m++

      }

  }

我们来假设 n 是8 那么 2³ 就是8 那么也就是 2的x次方就是 n 那么用大O 表示法就是O(log2ⁿ)

function fn(n) {
let m = 0
for (let i = 0; i < n; i *= 3) {

          m++

      }

  }

那么上面这段代码就很容易看出来是O(log3ⁿ) 了 我们忽略他的底数，都统一表示O(logn)

在这基础上O(nlogn) 就更好理解了，它表示的就是 一段 执行n遍的 logn复杂度的代码，我们把上面的代码稍稍修改一下

 function fn(n) {
for(let j =0;j<n;j++){
let m = 0
for (let i = 0; i < n; i *= 2) {

          m++

      }

   }

}

空间复杂度

其实空间复杂度 和时间复杂度 计算方式是一模一样的，只不过是着重的点不一样，当你回了时间复杂度的计算，空间复杂对你来说就是张飞吃豆芽了

   function fn(n) {
let m = []
for (let i = 0; i <= n; i = ++ ) {

         m.push(i)

      }

  }

这块代码我们关注他的空间使用 就知道 是O(n)了

案例分析

我们来举个前端中一个经典的复杂度优化的例子，react，vue 他们的diff算法。

要知道目前最好的 两棵树的完全比较，复杂度也还是O(n³) ，这对频繁触发更新的情况，是一个严重的瓶颈。 同样的问题也存在于 react中 useEffect 和useMemo 的dep 以及 memo 的props。

所以他们都将比较操作 只停留在了当前的一层，比如diff只比较 前后同一层级的节点变化，不同层级的变化比对在出发更新时做出决定，这样就可以始终把复杂度维持在O(n)

结语

其实你分析出来的复杂度不等于，代码真实的复杂度，不管是大O表示法也好 还是别的表示法也好，都是针对代码复杂度分析的一个抽象工具，比如有一段处理分页的代码的业务逻辑，你清清楚楚的知道，目前是不允许改变分页大小的，也就是每次调用最多传进来的只有10 条数据，但是代码写的复杂度是O(n²) 这时候其实是没有多大的影响的，但是假设你现在写了一个无线滚动的功能，每次加载还都需要对所有的数据做O(n²)的操作，那么这时候，你就需要去想想怎么做优化了