在 React 和 Vue 中，diff 算法声称从 O(n³) 优化到 O(n)，请解释 O(n³) 和 O(n) 各自是如何推导出来的？
考察说明
考查对虚拟 DOM diff 算法复杂度推导及优化策略的理解，是否掌握树编辑距离与启发式算法的区别。
回答思路
- 【回答框架 1】O(n³) 来自将两棵树的 diff 视为树编辑距离问题，最优解需要计算每个节点与其他节点的匹配，形成排列组合，动态规划复杂度可达 O(n³)。其中 n 是节点数，且假设树结构在比对中保持不变。
- 【回答框架 2】React 与 Vue 通过启发式策略将复杂度降至 O(n)：一是只对同层级节点进行比对，不跨层级移动；二是节点类型不同则直接替换整个子树；三是通过 key 标识节点，使同层列表的重排识别为移动而非重建。这样每层只需一次线性遍历，总复杂度为 O(n)。
- 【回答框架 3】React 的 diff 基于双端比较和 key 优化，Vue 也采用类似的同层比较与 key 优化，Vue 还使用了双端指针等策略。两者都牺牲了一定准确性以换取性能，不能保证在所有场景下均达到 O(n)，例如跨层移动节点时可能触发重建。
- 【回答框架 4】从实际角度看，O(n) 是平均情况下的复杂度，对于常见 UI 更新（如列表增删改），启发式算法非常高效。理解复杂度推导有助于在编写组件时合理使用 key 和保持组件结构稳定，避免不必要的性能开销。
- 【关键点 1】O(n³) 源自树编辑距离的通用算法，需要遍历节点间的所有可能匹配。
- 【关键点 2】同层比较、类型不同则替换、key 标识是复杂度降到 O(n) 的关键。
- 【关键点 3】O(n) 是平均或最优启发式复杂度，特定场景（如跨层移动）可能退化。
- 【易错点 1】误将 O(n) 视为严格保证，不考虑 key 缺失或类型变化的特殊情况。
- 【易错点 2】混淆 diff 与 reconciliation 的范围，diff 仅指对比过程，reconciliation 包含更新。
- 【易错点 3】简单认为复杂度降低必然带来性能提升，忽略实际渲染开销和组件生命周期影响。