传统diff算法的算法复杂度为什么是o(n3)?

小草べ
  • 43

react的diff 算法很厉害的样子~然后看了很多篇介绍~说是传统diff算法复杂是o(n3),都是从下面这个论文里的出来了,可是看了还是不清楚啊?有没有大神求教。。

论文算法详解:http://grfia.dlsi.ua.es/ml/al...

回复
阅读 9.4k
2 个回答

将两颗树中所有的节点一一对比需要O(n²)的复杂度,在对比过程中发现旧节点在新的树中未找到,那么就需要把旧节点删除,删除一棵树的一个节点(找到一个合适的节点放到被删除的位置)的时间复杂度为O(n),同理添加新节点的复杂度也是O(n),合起来diff两个树的复杂度就是O(n³)

宣传栏