# react或vue中diff时间复杂度
React 和 Vue 做的假设是：
- 检测VDOM的变化只发生在同一层
- 检测VDOM的变化依赖于用户指定的key
如果变化发生在不同层或者同样的元素用户指定了不同的key或者不同元素用户指定同样的key，React 和 Vue都不会检测到，就会发生莫名其妙的问题。
但是React 认为， 前端碰到上面的第一种情况概率很小，第二种情况又可以通过提示用户，让用户去解决，因此这个取舍是值得的。 没有牺牲空间复杂度，却换来了在大多数情况下时间上的巨大提升。
（1）传统diff
传统的diff是循环递归每一个节点。
比如左侧树a节点依次进行如下对比，左侧树节点b、c、d、e亦是与右侧树每个节点对比，算法复杂度能达到O(n^2)，查找完差异后还需计算最小转换方式，这其中的原理我没仔细去看，最终达到的算法复杂度是O(n^3)。
（2）react diff
传统diff算法复杂度达到O(n^3 )这意味着1000个节点就要进行数10亿次的比较，这是非常消耗性能的。react大胆的将diff的复杂度从O(n^3)降到了O(n)，它是如何做到的呢？
- 由于web UI中跨级移动操作非常少、可以忽略不计，所以react实现的diff是同层级比较
- 拥有相同类型的两个组件产生的DOM结构也是相似的，不同类型的两个组件产生的DOM结构则不近相同
- 对于同一层级的一组子节点，通过分配唯一唯一id进行区分（key值）
将所有的差异保存在了patches对象中，会有如下几种差异类型：
插入：patches[0]:{type:'INSERT_MARKUP',node: newNode }
移动：patches[0]: {type: 'MOVE_EXISTING'}
删除：patches[0]: {type: 'REMOVE_NODE'}
文本内容改变：patches[0]: {type: 'TEXT_CONTENT',content: 'virtual DOM2'}
属性改变：patches[0]: {type: 'SET_MARKUP',props: {className:''}}
（3）vue diff
跟react一样，只进行同层级比较，忽略跨级操作。