老师，为什么对比两棵树复杂度是 O(n ^ 3)呢？

Question

先遍历vdom1，
然后遍历vdom2
然后拿vdom1的每个属性与vdom2的每个属性进行对比排序？？？这里不是对比同层级的，而是一个层级与每个层级对比？

感觉这里没太听明白。。

Answer 1

双越 2020-04-06 20:54:43

第一，遍历树 A ，复杂度是 O(n)

第二，遍历树 B，复杂度是 O(n)

第三，对树的节点进行排序。这是可没说是同级别的，严格的树 diff ，是各个级别的都要移动排序，所以复杂度是 O(n)

三者嵌套起来，就会 O(n^3)

• 提问者 沧海的雨季 #1

  那么React 团队优化了算法，实现 O(n)。
  
   O(n)是只比较同一层级，跟O(n^3)区别是在哪啊？
  它不用遍历树A和树B在进行比较么？
  
  这一块儿好难理解啊。。

• 双越 回复 提问者 沧海的雨季 #2

  只在同一层级对比，而且根据 key 来判断，这样只遍历一遍即可。例如，开始遍历树 A ，遍历过程中就把树 B 的同层级节点进行对比了，待树 A 遍历完了，树 B 也就遍历完了，一遍完事儿。所以是 O(n)