知识点:
vm算法实现:

  • 4.1 步骤一:用JS对象模拟DOM树
  • 4.2 步骤二:比较两棵虚拟DOM树的差异 —— dom diff算法
  • 4.3 步骤三:把差异应用到真正的DOM树上

dom diff

理想的dom diff = 位移O(n³) // 递归对各节点增删移
简化的O(n)diff = 删除 + 新增
只按层比较,就可以将时间复杂度降低为 O(n)
按层比较也不是广度遍历,其实就是判断某个节点的子元素间 diff跨父节点的兄弟节点也不必比较

这样做确实非常高效,但代价就是,判断的有点傻,比如 ac 明明是一个移动操作,却被误识别为删除 + 新增。
好在跨 DOM 复用在实际业务场景中很少出现

同层 diff 可能出现的三种情况

Vue 使用了一种贪心 + 二分的算法求出最长上升子序列

参考资料