Vue的diff时间复杂度如何从O(n^3)优化到 O(n)？vue2和vue3 diff 有什么差异？

[GGXXMM]

比较两个树的变化，最简单的比较算法是递归处理，时间复杂度是O(n^3)，leetcode有相应题目可以帮助理解。

Vue的diff算法如何将时间复杂度优化到O(n)？

在前端中，很少会跨域层级地移动DOM元素。diff算法是通过同层的树节点进行比较而非对树进行逐层搜索遍历的方式，所以时间复杂度只有O(n)，是一种相当高效的算法。

vue2 diff

1. 头和头比
2. 尾和尾比
3. 头和尾比
4. 尾和头比
5. 都没有命中的对比

参考：https://github.com/answershuto/VueDemo/blob/master/%E3%80%8A%E6%95%B0%E6%8D%AE%E7%8A%B6%E6%80%81%E6%9B%B4%E6%96%B0%E6%97%B6%E7%9A%84%E5%B7%AE%E5%BC%82%20diff%20%E5%8F%8A%20patch%20%E6%9C%BA%E5%88%B6%E3%80%8B.js

vue3 diff

1. 头和头比
2. 尾和尾比
3. 基于最长递增子序列进行移动/添加/删除

vue2 vs vue3 diff

在 Vue2 中，头尾比对和尾头比对就算发现新老节点是属于 sameVnode 时还是需要进行节点位置的移动。另外在没有命中 1-4 步骤的情况下进行新旧节点的映射关系查找再进行位置移动也不是性能最优的方式。最优的方式本小节已经讲解到，就是基于最长递增子序列进行移动/添加/删除。

在 Vue3 中，基于最长递增子序列进行移动/添加/删除 的diff更新，已经涵盖了 Vue2 的 3-5 步骤，而且性能是最优解。所以相对于 Vue2，Vue3 在diff算法方面做了很大的优化工作。

参考：https://zhuanlan.zhihu.com/p/443971566