写在前面
此系列来源于开源项目：前端 100 问：能搞懂 80%的请把简历给我
为了备战 2021 春招
每天一题，督促自己
从多方面多角度总结答案，丰富知识
React 和 Vue 的 diff 时间复杂度从 O(n^3) 优化到 O(n) ，那么 O(n^3) 和 O(n) 是如何计算出来的？
简书整合地址：前端 100 问
正文回答
原问题标题“React 和 Vue 的 diff 时间复杂度从 O(n^3) 优化到 O(n) ，那么 O(n^3) 和 O(n) 是如何计算出来的？ ”
- 这里的 n 指的是页面的 VDOM 节点数，这个不太严谨。如果更严谨一点，我们应该假设变化之前的节点数为 m，变化之后的节点数为 n。
- React 和 Vue 做优化的前提是“放弃了最优解“，本质上是一种权衡，有利有弊。
React 和 Vue 做的假设是：
- 检测 VDOM 的变化只发生在同一层
- 检测 VDOM 的变化依赖于用户指定的 key
如果变化发生在不同层或者同样的元素用户指定了不同的 key 或者不同元素用户指定同样的 key，React 和 Vue 都不会检测到，就会发生莫名其妙的问题。
但是 React 认为，前端碰到上面的第一种情况概率很小，第二种情况又可以通过提示用户，让用户去解决，因此这个取舍是值得的。 没有牺牲空间复杂度，却换来了在大多数情况下时间上的巨大提升。
基本概念
其实这是一个典型的最小编辑距离的问题，相关算法有很多，比如 Git 中，提交之前会进行一次对象的 diff 操作，就是用的这个最小距离编辑算法。
对于树，我们也是一样的，我们定义三种操作，用来将一棵树转化为另外一棵树：
- 删除：删除一个节点，将它的 children 交给它的父节点
- 插入：在 children 中 插入一个节点
- 修改：修改节点的值
事实上，从一棵树转化为另外一棵树，我们有很多方式，我们要找到最少的。
直观的方式是用动态规划，通过这种记忆化搜索减少时间复杂度。
确切地说，树的最小距离编辑算法的时间复杂度是 O(n^2m(1+logmn)),
我们假设 m 与 n 同阶， 就会变成 O(n^3)。
大佬回答
Virtual DOM render + diff 显然比渲染 html 字符串要慢，但是！它依然是纯 js 层面的计算，比起后面的 DOM 操作来说，依然便宜了太多。可以看到，innerHTML 的总计算量不管是 js 计算还是 DOM 操作都是和整个界面的大小相关，但 Virtual DOM 的计算量里面，只有 js 计算和界面大小相关，DOM 操作是和数据的变动量相关的。前面说了，和 DOM 操作比起来，js 计算是极其便宜的。
这才是为什么要有 Virtual DOM：它保证了 1）不管你的数据变化多少，每次重绘的性能都可以接受；2) 你依然可以用类似 innerHTML 的思路去写你的应用。
