第 97 题：React 和 Vue 的 diff 时间复杂度从 O(n^3) 优化到 O(n) ，那么 O(n^3) 和 O(n) 是如何计算出来的？
yygmind opened this issue · 34 comments
好问题:fist:
我理解的是：react对比按照树的层级去对比，给树节点编号0，1，2，3...，相同编号对比，不一样就直接删除然后，添加新节点，
react只做了同层比较，同级的节点类型不同就认为不同，重新渲染。
我认为react做了三种优化来降低复杂度：1：如果父节点不同，放弃对子节点的比较，直接删除旧节点然后添加新的节点重新渲染；2：如果子节点有变化，Virtual DOM不会计算变化的是什么，而是重新渲染，3：通过唯一的key策略
我知道，但是我就是不说
我知道，但是我就是不说
调皮
知乎：https://www.zhihu.com/question/66851503
从一棵树转化为另外一棵树,直观的方式是用动态规划，通过这种记忆化搜索减少时间复杂度。由于树是一种递归的数据结构，因此最简单的树的比较算法是递归处理。确切地说，树的最小距离编辑算法的时间复杂度是 O(n^2m(1+logmn)), 我们假设 m 与 n 同阶， 就会变成 O(n^3)。
谈一下理解：
主要看了vue 的diff 算法：
O(n) 代表如果有n节点需要更新，只需要操作dom n 次就能完成。 但是这里有个前提是 这n个节点更新后和原来dom 要在同层，如果跨层更新节点，肯定比O(n)复杂。
至于O(n^3)怎么来的不是很清楚。。。
参考的文章：aooy/blog#2
关于O(n^3)怎么计算出来的
问题描述
原问题标题“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操作，就是用的这个最小距离编辑算法。
leetcode 有原题目,
如果想明白这个O(n^3)， 可以先看下这个。
对于树，我们也是一样的，我们定义三种操作，用来将一棵树转化为另外一棵树：
-
删除：删除一个节点，将它的children交给它的父节点
-
插入：在children中 插入一个节点
-
修改：修改节点的值
事实上，从一棵树转化为另外一棵树，我们有很多方式，我们要找到最少的。
直观的方式是用动态规划，通过这种记忆化搜索减少时间复杂度。
算法
由于树是一种递归的数据结构，因此最简单的树的比较算法是递归处理。
详细描述这个算法可以写一篇很长的论文，这里不赘述。
大家想看代码的，这里有一份
我希望没有吓到你。
确切地说，树的最小距离编辑算法的时间复杂度是O(n^2m(1+logmn)),
我们假设m 与 n 同阶， 就会变成 O(n^3)。
题外话
大家如果对数据结构和算法感兴趣，可以关注下我的leetcode题解
React 从来没有说过 “React 比原生操作 DOM 快”。React 的基本思维模式是每次有变动就整个重新渲染整个应用。如果没有 Virtual DOM，简单来想就是直接重置 innerHTML。很多人都没有意识到，在一个大型列表所有数据都变了的情况下，重置 innerHTML 其实是一个还算合理的操作... 真正的问题是在 “全部重新渲染” 的思维模式下，即使只有一行数据变了，它也需要重置整个 innerHTML，这时候显然就有大量的浪费。
我们可以比较一下 innerHTML vs. Virtual DOM 的重绘性能消耗：
-
innerHTML: render html string O(template size) + 重新创建所有 DOM 元素 O(DOM size)。
-
Virtual DOM: render Virtual DOM + diff O(template size) + 必要的 DOM 更新 O(DOM change)。
Virtual DOM render + diff 显然比渲染 html 字符串要慢，但是！它依然是纯 js 层面的计算，比起后面的 DOM 操作来说，依然便宜了太多。可以看到，innerHTML 的总计算量不管是 js 计算还是 DOM 操作都是和整个界面的大小相关，但 Virtual DOM 的计算量里面，只有 js 计算和界面大小相关，DOM 操作是和数据的变动量相关的。前面说了，和 DOM 操作比起来，js 计算是极其便宜的。
这才是为什么要有 Virtual DOM：它保证了 1）不管你的数据变化多少，每次重绘的性能都可以接受；2) 你依然可以用类似 innerHTML 的思路去写你的应用。
作者：尤雨溪
链接：https://www.zhihu.com/question/31809713/answer/53544875
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
这个问题做算法分析的都很难在面试的时候说明白的。不知道哪家公司会问这种问题。
我知道，但是我就是不说
臭弟弟，宁可别给我逮着了
关于O(n^3)怎么计算出来的
问题描述
原问题标题“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操作，就是用的这个最小距离编辑算法。leetcode 有原题目,
如果想明白这个O(n^3)， 可以先看下这个。对于树，我们也是一样的，我们定义三种操作，用来将一棵树转化为另外一棵树：
- 删除 删除一个节点，将它的children交给它的父节点
- 插入 在children中 插入一个节点
- 修改 修改节点的值
事实上，从一棵树转化为另外一棵树，我们有很多方式，我们要找到最少的。
直观的方式是用动态规划，通过这种记忆化搜索减少时间复杂度。
算法
由于树是一种递归的数据结构，因此最简单的树的比较算法是递归处理。
详细描述这个算法可以写一篇很长的论文，这里不赘述。
大家想看代码的，这里有一份
我希望没有吓到你。确切地说，树的最小距离编辑算法的时间复杂度是
O(n^2m(1+logmn)),
我们假设m 与 n 同阶， 就会变成O(n^3)。题外话
大家如果对数据结构和算法感兴趣，可以关注下我的leetcode题解
你吓到我了
diff策略
React用 三大策略 将O(n^3)复杂度 转化为 O(n)复杂度
策略一（tree diff）：
Web UI中DOM节点跨层级的移动操作特别少，可以忽略不计。
策略二（component diff）：
拥有相同类的两个组件 生成相似的树形结构，
拥有不同类的两个组件 生成不同的树形结构。
策略三（element diff）：
对于同一层级的一组子节点，通过唯一id区分。
没看懂你们的回答在答什么，原来的O(n^3)是怎样的，然后通过什么策略变成了O(n)的？
这个问题做算法分析的都很难在面试的时候说明白的。不知道哪家公司会问这种问题。
昨晚我就被字节问了，问的很深
没看懂你们的回答在答什么，原来的O(n^3)是怎样的，然后通过什么策略变成了O(n)的？
问题只是问3次方怎么计算，没有说 n 怎么优化的哦
话说回来 react 的 diff 应该是 O(2n) 吧，第一次 n 是新树一对一节点对比老树，第二次 n 是应用 patches ....
没看懂你们的回答在答什么，原来的O(n^3)是怎样的，然后通过什么策略变成了O(n)的？
原来的 O(n^3) 的 diff 流程是：
- 老树的每一个节点都去遍历新树的节点，直到找到新树对应的节点。那么这个流程就是 O(n^2)，再紧接着找到不同之后，再计算最短修改距离然后修改节点，这里是 O(n^3)
个人猜想：
- 对于两棵树的比较，最简单的就是遍历，两层嵌套就是 O(n^2)
- 假设每个节点都要做更新操作，那就是再加个 O(n)。加起来就是 O(n^3)
vue的更新策略就是：深度优先、同层比较。就是只比较同层级，也就是 O(n)
这个问题做算法分析的都很难在面试的时候说明白的。不知道哪家公司会问这种问题。
海康威视
- 同一层级节点进行比较
- 节点的标签是否相同，相同不再进行比较，不同直接删除重新创建节
- 节点的标签和key是否相同， 相同不再进行比较，不同直接删除重新创建节点
这个问题做算法分析的都很难在面试的时候说明白的。不知道哪家公司会问这种问题。
火花思维有问到
React 和 Vue 做的假设是：
- 检测VDOM的变化只发生在同一层
- 检测VDOM的变化依赖于用户指定的key
@azl397985856 根据 key 来进行比较，这个过程的复杂度不是 O(k1 * k2) 的吗 (k1, k2 分别为新旧子元素列表长度）；即便使用 Map / Hash 优化，也应该是 O(k1 log(k2))，好像也达不到 O(N) 的复杂度
我知道，但是我就是不说
你真坏
打你小屁屁
为了降低算法复杂度，React的diff会预设三个限制：
只对同级元素进行Diff。如果一个DOM节点在前后两次更新中跨越了层级，那么React不会尝试复用他。
两个不同类型的元素会产生出不同的树。如果元素由div变为p，React会销毁div及其子孙节点，并新建p及其子孙节点。
开发者可以通过 key prop来暗示哪些子元素在不同的渲染下能保持稳定。
我也被问到了，滴滴
O(n^3)是指两棵树diff时：
- 遍历第一棵树，在第一棵树的遍历中再去遍历第二颗树，找出各个节点diff出的结果并记录到一个数组中，这里头操作的时间复杂度是O(n^2)
- 遍历diff记录的数组，并对第一棵树的diff位置做增删改操作，时间复杂度O(n)
O(n^3) = O(n) * O(n^2)得出，涉及了跨层级对比计算出的结果。
而React优化后的O(n^2)只做了同级diff，如果同级（位置）diff不同，则删除原节点再重新生成一个新节点，所以时间复杂度是O(n)
我们知道，两棵树做 diff，复杂度是 O(n^3) 的，因为每个节点都要去和另一棵树的全部节点对比一次，这就是 n 了，如果找到有变化的节点，执行插入、删除、修改也是 n 的复杂度。所有的节点都是这样，再乘以 n，所以是 O(n * n * n) 的复杂度。
这样的复杂度对于前端框架来说是不可接受的，这意味着 1000 个节点，渲染一次就要处理 1000 * 1000 * 1000，一共 10 亿次。
所以前端框架的 diff 约定了两种处理原则：只做同层的对比，type 变了就不再对比子节点。
因为 dom 节点做跨层级移动的情况还是比较少的，一般情况下都是同一层级的 dom 的增删改。
这样只要遍历一遍，对比一下 type 就行了，是 O(n) 的复杂度，而且 type 变了就不再对比子节点，能省下一大片节点的遍历。另外，因为 vdom 中记录了关联的 dom 节点，执行 dom 的增删改也不需要遍历，是 O(1)的，整体的 diff 算法复杂度就是 O(n) 的复杂度。
--神光的编程秘籍 https://mp.weixin.qq.com/s/mFGT6szPzYuCaz1Rgvt9TQ
这个问题做算法分析的都很难在面试的时候说明白的。不知道哪家公司会问这种问题。
火花思维有问到
你说的火花思维是做儿童教育的
React 从来没有说过 “React 比原生操作 DOM 快”。React 的基本思维模式是每次有变动就整个重新渲染整个应用。如果没有 Virtual DOM，简单来想就是直接重置 innerHTML。很多人都没有意识到，在一个大型列表所有数据都变了的情况下，重置 innerHTML 其实是一个还算合理的操作... 真正的问题是在 “全部重新渲染” 的思维模式下，即使只有一行数据变了，它也需要重置整个 innerHTML，这时候显然就有大量的浪费。 我们可以比较一下 innerHTML vs. Virtual DOM 的重绘性能消耗：
- innerHTML: render html string O(template size) + 重新创建所有 DOM 元素 O(DOM size)。
- Virtual DOM: render Virtual DOM + diff O(template size) + 必要的 DOM 更新 O(DOM change)。
Virtual DOM render + diff 显然比渲染 html 字符串要慢，但是！它依然是纯 js 层面的计算，比起后面的 DOM 操作来说，依然便宜了太多。可以看到，innerHTML 的总计算量不管是 js 计算还是 DOM 操作都是和整个界面的大小相关，但 Virtual DOM 的计算量里面，只有 js 计算和界面大小相关，DOM 操作是和数据的变动量相关的。前面说了，和 DOM 操作比起来，js 计算是极其便宜的。
这才是为什么要有 Virtual DOM：它保证了 1）不管你的数据变化多少，每次重绘的性能都可以接受；2) 你依然可以用类似 innerHTML 的思路去写你的应用。
作者：尤雨溪 链接：https://www.zhihu.com/question/31809713/answer/53544875 来源：知乎 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
这个好像偏题了啊 不是楼主问的..