React 中的 dom diff 算法如何从 O(n3) 优化到 O(n) 的
Issue 欢迎在 Gtihub Issue 中回答此问题: Issue 410
Author 回答者: shfshanyue
参考官方文档: 协调的设计动机
此算法有一些通用的解决方案，即生成将一棵树转换成另一棵树的最小操作次数。然而，即使使用最优的算法，该算法的复杂程度仍为 O(n 3 )，其中 n 是树中元素的数量。
如果在 React 中使用该算法，那么展示 1000 个元素则需要 10 亿次的比较。这个开销实在是太过高昂。于是 React 在以下两个假设的基础之上提出了一套 O(n) 的启发式算法：
- 两个不同类型的元素会产生出不同的树；
- 开发者可以通过设置 key 属性，来告知渲染哪些子元素在不同的渲染下可以保存不变；
在实践中，我们发现以上假设在几乎所有实用的场景下都成立。