React中有提到的传统diff算法时间复杂度O(n^3)？

Question

React中有提到的传统 diff 算法时间复杂度O(n^3)？
这是怎么算额？

Answer 1

树的变换操作算法，论文研究出来的：A survey on tree edit distance and related problems

React用的方式理论上是 O(n) ，因为加了一些限制和辅助(key)。

相关：https://reactjs.org/docs/reco...

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...。