为什么 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假定所有的比较都在同级进行，这样当然就会使得计算复杂度大大降低。具体的实现方式，可以参考这篇文章。我也只是个搬运工。