为什么 react 的diff 算法 到 传统的树节点比较算法 从O(n^3)到 O(n) ？

Question

为什么 react 的diff 算法 到 传统的树节点比较算法 从O(n^3)到 O(n) ，请问 O(n^3) 和O(n) 是怎么计算出来的 ？

Answer 1

关于时间复杂度的计算，这篇文章讲的很清楚，我建议你好好读一读。

至于说为什么传统的树节点比较算法的时间复杂度是O(n^3)，而react的diff算法只需要O(n)，这是因为react对树节点的比较做了很大的前提假设，限定死了很多东西，不做过于复杂的计算操作，所以降低了复杂度。而传统的树节点要做非常完整的检查，比如说比较不同级别的树状结构，在传统算法里是需要考虑的，而react假定所有的比较都在同级进行，这样当然就会使得计算复杂度大大降低。

具体的实现方式，可以参考这篇文章。我也只是个搬运工。

Answer 2

react树对比是按照层级去对比的， 他会给树编号0,1,2,3,4.... 然后相同的编号进行比较。 所以复杂度是n，这个好理解。

关键是传统diff的复杂度是怎么算的？ 传统的diff需要出了上面的比较之外，还需要跨级比较。 他会将两个数的
节点，两两比较，这就有n^2的复杂度了。 然后还需要编辑树，编辑的树可能发生在任何节点，需要对树进行再一次遍历操作，因此复杂度为n。加起来就是n^3了。 我这里不涉及严谨推理过程，只是给大家一个感性的认识而已。 如有错误，概不负责。

这里有一个回答，也可以参考一下react的

diff 从O(n^3)到 O(n) ，请问 O(n^3) 和O(n) 是怎么算出来？ - COIN的回答 - 知乎
https://www.zhihu.com/questio...。