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

来源：4-9 虚拟DOM-diff算法概述

沧海的雨季

2020-04-06

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

感觉这里没太听明白。。

写回答

1回答

双越

2020-04-06

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

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

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

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

双越

沧海的雨季

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

2020-04-06

共2条回复

2024版前端框架及项目面试聚焦Vue3/React/Webpack

面向1-3年前端的框架及项目面试“刚需内容”

4664 学习 · 1644 问题

相似问题

回答 1

回答 2

回答 2

回答 1

回答 1