第 97 题：React 和 Vue 的 diff 时间复杂度从 O(n^3) 优化到 O(n) ，那么 O(n^3) 和 O(n) 是如何计算出来的？

[yygmind]

[yingye]

好问题:fist:

[Mohannnnn]

我理解的是：react对比按照树的层级去对比，给树节点编号0，1，2，3...，相同编号对比，不一样就直接删除然后，添加新节点，

[rocky-191]

react只做了同层比较，同级的节点类型不同就认为不同，重新渲染。

[Jenear]

我认为react做了三种优化来降低复杂度：1：如果父节点不同，放弃对子节点的比较，直接删除旧节点然后添加新的节点重新渲染；2：如果子节点有变化，Virtual DOM不会计算变化的是什么，而是重新渲染，3：通过唯一的key策略

[azl397985856]

我知道，但是我就是不说

[chenzesam]

我知道，但是我就是不说

调皮

[libin1991]

知乎：https://www.zhihu.com/question/66851503

从一棵树转化为另外一棵树,直观的方式是用动态规划，通过这种记忆化搜索减少时间复杂度。由于树是一种递归的数据结构，因此最简单的树的比较算法是递归处理。确切地说，树的最小距离编辑算法的时间复杂度是 O(n^2m(1+logmn)), 我们假设 m 与 n 同阶， 就会变成 O(n^3)。

[nano-papa]

Dads 原始邮件 发件人: Zhilin<notifications@github.com> 收件人: Advanced-Frontend/Daily-Interview-Question<Daily-Interview-Question@noreply.github.com> 抄送: Subscribed<subscribed@noreply.github.com> 发送时间: 2019年7月10日(周三) 18:37 主题: Re: [Advanced-Frontend/Daily-Interview-Question] 第 97 题：React 和 Vue 的 diff 时间复杂度从 O(n^3) 优化到 O(n) ，那么 O(n^3) 和 O(n) 是如何计算出来的？ (#151) 我知道，但是我就是不说 你真坏 死鬼 — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub<#151?email_source=notifications&email_token=AE2P5FJGNTWVJXOEOVPP7DLP6W3YHA5CNFSM4H4TKCU2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODZTB2BY#issuecomment-510008583>, or mute the thread<https://github.com/notifications/unsubscribe-auth/AE2P5FMB4TIKAG22GM222J3P6W3YHANCNFSM4H4TKCUQ>.

[bobohuochai]

谈一下理解：
主要看了vue 的diff 算法：
O(n) 代表如果有n节点需要更新，只需要操作dom n 次就能完成。 但是这里有个前提是 这n个节点更新后和原来dom 要在同层，如果跨层更新节点，肯定比O(n)复杂。
至于O(n^3)怎么来的不是很清楚。。。
参考的文章：aooy/blog#2

[azl397985856]

关于O(n^3)怎么计算出来的

问题描述

原问题标题“React 和 Vue 的 diff 时间复杂度从 O(n^3) 优化到 O(n) ，那么 O(n^3) 和 O(n) 是如何计算出来的？ ”

1. 这里的n指的是页面的VDOM节点数，这个不太严谨。如果更严谨一点，我们应该应该假设
   变化之前的节点数为m，变化之后的节点数为n。

2. 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题解

[15957787988]

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
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

[leoni121]

传统diff、react优化diff、vue优化diff

[jrt8]

这个问题做算法分析的都很难在面试的时候说明白的。不知道哪家公司会问这种问题。