react的diff 算法很厉害的样子~然后看了很多篇介绍~说是传统diff算法复杂是o(n3),都是从下面这个论文里的出来了,可是看了还是不清楚啊?有没有大神求教。。
react的diff 算法很厉害的样子~然后看了很多篇介绍~说是传统diff算法复杂是o(n3),都是从下面这个论文里的出来了,可是看了还是不清楚啊?有没有大神求教。。
8 回答4.7k 阅读✓ 已解决
6 回答3.4k 阅读✓ 已解决
5 回答2.8k 阅读✓ 已解决
5 回答6.3k 阅读✓ 已解决
4 回答2.3k 阅读✓ 已解决
4 回答2.8k 阅读✓ 已解决
3 回答2.5k 阅读✓ 已解决
将两颗树中所有的节点一一对比需要O(n²)的复杂度,在对比过程中发现旧节点在新的树中未找到,那么就需要把旧节点删除,删除一棵树的一个节点(找到一个合适的节点放到被删除的位置)的时间复杂度为O(n),同理添加新节点的复杂度也是O(n),合起来diff两个树的复杂度就是O(n³)