React 中的 DOM diff 算法如何优化到 O (n)?

描述 React 如何将传统的 O (n^3) DOM diff 复杂度优化为 O (n)，并分析其三个关键策略：树分层比较、组件类型识别和唯一 ID 复用。

React 困难 性能优化 DOM 性能

传统 diff 算法涉及循环递归比较 DOM 树中所有节点的父子关系，复杂度为 O(n^3)，计算开销过大。 React 通过三方面的优化策略将复杂度降为 O(n)，核心在于以下假设驱动的设计:

  1. 树分层比较策略（Tree Diff）:
    假设 DOM 节点较少跨层级移动，只对比同级节点，跳过异层节点的跨域计算。
    当发现节点不存在于新树同层级时，会直接删除旧节点及其子节点；遍历只需一次 O(n) 操作.

  2. 组件类型识别策略（Component Diff）:
    同类型组件（如相同 class）会进行递归子节点比较；不同组件直接视作生成全新 DOM，删除旧组件，无需深究匹配关系，仅需 O(1) 复杂度的创建或销毁。

  3. 唯一 ID 复用策略（Element Diff）:
    比较同一层级子节点时，通过 key 属性区分节点，避免顺序移动的重复计算:
    使用插入、移动或删除操作处理节点变化，而非法为 O(n) 的全递归对比:

    // 例如列表渲染时用 key 优化 diff
function Component({ items }) {
  return items.map(item => <div key={item.id}>{item.name}</div>);
}

    复杂度减少为 O(n)： Tree Diff 层遍历需 O(n)，Element Diff 基于高效节点 ID 仅需线性匹配；整体仅当同级结构改变才增加极小开销.