首頁猿問為什么 react 的diff...

為什么 react 的diff 算法到傳統(tǒng)的樹節(jié)點(diǎn)比較算法從O(n^3)到 O(n) ？

React.JS

長風(fēng)秋雁 2018-10-24 07:53:56

為什么 react 的diff 算法到傳統(tǒng)的樹節(jié)點(diǎn)比較算法從O(n^3)到 O(n) ，請問 O(n^3) 和O(n) 是怎么計(jì)算出來的？

查看完整描述

2 回答

阿波羅的戰(zhàn)車

TA貢獻(xiàn)1862條經(jīng)驗(yàn) 獲得超6個(gè)贊

關(guān)于時(shí)間復(fù)雜度的計(jì)算，這篇文章講的很清楚，我建議你好好讀一讀。

至于說為什么傳統(tǒng)的樹節(jié)點(diǎn)比較算法的時(shí)間復(fù)雜度是O(n^3)，而react的diff算法只需要O(n)，這是因?yàn)閞eact對樹節(jié)點(diǎn)的比較做了很大的前提假設(shè)，限定死了很多東西，不做過于復(fù)雜的計(jì)算操作，所以降低了復(fù)雜度。而傳統(tǒng)的樹節(jié)點(diǎn)要做非常完整的檢查，比如說比較不同級別的樹狀結(jié)構(gòu)，在傳統(tǒng)算法里是需要考慮的，而react假定所有的比較都在同級進(jìn)行，這樣當(dāng)然就會使得計(jì)算復(fù)雜度大大降低。

具體的實(shí)現(xiàn)方式，可以參考這篇文章。我也只是個(gè)搬運(yùn)工。

反對回復(fù) 2018-10-24