阅读 768

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题解](github.com/azl39798585…

关注下面的标签,发现更多相似文章
评论