# react Diff ## 1. 作用 计算出Virtual DOM中真正变化的部分， 并只针对该部分进行原生DOM操作，而非重新渲染整个页面。 ## 2. 相对于传统的 diff 算法 通过循环递归对节点进行依次对比，算法复杂度达到 **O(n^3)** ，n是树的节点数。 ### 2.1: O(n^3)怎么计算出来的 1. ***原问题标题“React 和 Vue 的 diff 时间复杂度从 O(n^3) 优化到 O(n) ，那么 O(n^3) 和 O(n) 是如何计算出来的？ ”*** 这里的n指的是页面的VDOM节点数，这个不太严谨。如果更严谨一点，我们应该应该假设 **变化之前的节点数为m，变化之后的节点数为n。** 2. 倘若这个算法用到别的行业，比如医药行业，肯定是不行的，为什么？ React 和 Vue 做的假设是： * 检测VDOM的变化只发生在同一层 * 检测VDOM的变化依赖于用户指定的key 3. 如果变化发生在**不同层**或者同样的元素用户指定了**不同的key**或者不同元素用户指定**同样的key**， React 和 Vue都不会检测到，就会发生莫名其妙的问题。 4. 由于树是一种递归的数据结构，最简单的树的比较算法是递归处理，确切地说，树的最小距离编辑算法的时间复杂度是`O(n^2m(1+logmn))`, 我们假设`m 与 n 同阶`， 就会变成`O(n^3)`。 ## 3. key的作用是为了在diff算法执行时更快的找到对应的节点，提高diff速度