简述React 和 Vue 的 diff 时间复杂度从 O(n^3) 优化 到 O(n) ，那么 O(n^3) 和 O(n) 是如何计算出来的 ？

React 和 Vue 的 diffing 算法（即虚拟DOM比较算法）的优化过程是一个复杂的过程，涉及到多个层面的设计和优化。从 O(n^3) 优化到 O(n) 的时间复杂度并不是简单地通过一个步骤完成的，而是经过了一系列的改进和优化。

O(n^3) 的可能来源

变成O(n^3)其实是牺牲了最优解，来换取时间

在最初的虚拟DOM diffing算法中，如果采用简单的方法去比较两个树形结构的差异，可能会遇到需要递归比较所有节点的情况。在最坏的情况下，每个节点都需要与其对应的节点以及所有子节点进行比较，这可能导致一个三重循环（对于每个节点，检查其子节点，然后对于每个子节点再检查其子节点），从而可能产生 O(n^3) 的时间复杂度。

优化到 O(n) 的过程

React 和 Vue 都采用了不同的策略来优化 diffing 算法，使其时间复杂度降低到接近 O(n)。以下是一些常见的优化策略：

1. 基于组件类型的比较：

   • 如果两个节点是不同类型的，React 会立即销毁旧的树并构建新的树。
   • Vue 也类似，它会基于虚拟节点的类型来判断是否可以复用节点。