關于時間復雜度的計算，這篇文章講的很清楚，我建議你好好讀一讀。

至于說為什么傳統的樹節點比較算法的時間復雜度是O(n^3)，而react的diff算法只需要O(n)，這是因為react對樹節點的比較做了很大的前提假設，限定死了很多東西，不做過于復雜的計算操作，所以降低了復雜度。而傳統的樹節點要做非常完整的檢查，比如說比較不同級別的樹狀結構，在傳統算法里是需要考慮的，而react假定所有的比較都在同級進行，這樣當然就會使得計算復雜度大大降低。

具體的實現方式，可以參考這篇文章。我也只是個搬運工。