简述React 和 Vue 的 diff 时间复杂度从 O(n^3) 优化 到 O(n) ，那么 O(n^3) 和 O(n) 是如何计算出来的 ？
在讨论这个问题之前，我们需要先理解什么是时间复杂度。时间复杂度是用来估计算法运行时间的一个表达式，它描述的是算法运行时间与输入数据之间的关系。常见的时间复杂度有 O(1)、O(n)、O(n^2)、O(n^3)、O(logn)、O(nlogn) 等。
对于 O(n^3) 的时间复杂度，这是指算法运行的时间与输入数据的立方成正比。对于 O(n) 的时间复杂度，这是指算法运行的时间与输入数据的线性成正比。
在早期的差异算法中，最简单的实现方式是深度优先遍历，对每一个节点进行一次比较，这样的算法时间复杂度就是 O(n^3)，其中 n 是节点数量。
为了提高效率，React 和 Vue 都采用了一种优化的差异算法，将时间复杂度降低到了 O(n)。这个优化主要是基于两个假设：
- 两个相同的组件会产生类似的树形结构，不同的组件会产生不同的树形结构。
- 对于同一层级的一组子节点，它们可以通过唯一 id 进行区分。
基于这两个假设，React 和 Vue 在进行 diff 的时候，首先会比较两棵树的根节点，然后再比较它们的子节点。在比较子节点的时候，它们会通过唯一 id 来区分不同的子节点，这样就可以避免了深度遍历，大大提高了效率。
所以，React 和 Vue 的 diff 算法的时间复杂度是 O(n)，其中 n 是节点数量。