寫在前面
此系列來源于開源項目：前端 100 問：能搞懂 80%的請把簡歷給我
為了備戰(zhàn) 2021 春招
每天一題摆马，督促自己
從多方面多角度總結(jié)答案臼闻，豐富知識
React 和 Vue 的 diff 時間復(fù)雜度從 O(n^3) 優(yōu)化到 O(n) ，那么 O(n^3) 和 O(n) 是如何計算出來的囤采？
簡書整合地址：前端 100 問
正文回答
原問題標(biāo)題“React 和 Vue 的 diff 時間復(fù)雜度從 O(n^3) 優(yōu)化到 O(n) 述呐，那么 O(n^3) 和 O(n) 是如何計算出來的？ ”
- 這里的 n 指的是頁面的 VDOM 節(jié)點數(shù)蕉毯，這個不太嚴(yán)謹(jǐn)乓搬。如果更嚴(yán)謹(jǐn)一點思犁，我們應(yīng)該假設(shè)變化之前的節(jié)點數(shù)為 m，變化之后的節(jié)點數(shù)為 n进肯。
- React 和 Vue 做優(yōu)化的前提是“放棄了最優(yōu)解“激蹲，本質(zhì)上是一種權(quán)衡，有利有弊江掩。
React 和 Vue 做的假設(shè)是：
- 檢測 VDOM 的變化只發(fā)生在同一層
- 檢測 VDOM 的變化依賴于用戶指定的 key
如果變化發(fā)生在不同層或者同樣的元素用戶指定了不同的 key 或者不同元素用戶指定同樣的 key学辱，React 和 Vue 都不會檢測到，就會發(fā)生莫名其妙的問題频敛。
但是 React 認(rèn)為项郊，前端碰到上面的第一種情況概率很小，第二種情況又可以通過提示用戶斟赚，讓用戶去解決着降，因此這個取舍是值得的。 沒有犧牲空間復(fù)雜度拗军，卻換來了在大多數(shù)情況下時間上的巨大提升任洞。
基本概念
其實這是一個典型的最小編輯距離的問題，相關(guān)算法有很多发侵，比如 Git 中交掏，提交之前會進(jìn)行一次對象的 diff 操作，就是用的這個最小距離編輯算法刃鳄。
對于樹盅弛，我們也是一樣的，我們定義三種操作叔锐，用來將一棵樹轉(zhuǎn)化為另外一棵樹：
- 刪除：刪除一個節(jié)點挪鹏，將它的 children 交給它的父節(jié)點
- 插入：在 children 中 插入一個節(jié)點
- 修改：修改節(jié)點的值
事實上，從一棵樹轉(zhuǎn)化為另外一棵樹愉烙，我們有很多方式讨盒，我們要找到最少的。
直觀的方式是用動態(tài)規(guī)劃步责，通過這種記憶化搜索減少時間復(fù)雜度返顺。
確切地說，樹的最小距離編輯算法的時間復(fù)雜度是 O(n^2m(1+logmn)),
我們假設(shè) m 與 n 同階蔓肯， 就會變成 O(n^3)遂鹊。
大佬回答
Virtual DOM render + diff 顯然比渲染 html 字符串要慢，但是蔗包！它依然是純 js 層面的計算稿辙，比起后面的 DOM 操作來說，依然便宜了太多气忠×诖ⅲ可以看到赋咽，innerHTML 的總計算量不管是 js 計算還是 DOM 操作都是和整個界面的大小相關(guān)，但 Virtual DOM 的計算量里面吨娜，只有 js 計算和界面大小相關(guān)脓匿，DOM 操作是和數(shù)據(jù)的變動量相關(guān)的。前面說了宦赠，和 DOM 操作比起來陪毡，js 計算是極其便宜的。
這才是為什么要有 Virtual DOM：它保證了 1）不管你的數(shù)據(jù)變化多少勾扭，每次重繪的性能都可以接受毡琉；2) 你依然可以用類似 innerHTML 的思路去寫你的應(yīng)用。
