原文鏈接：https://juejin.im/post/6892671384976097287

很多文章提到的都是新舊DOM樹需要兩兩對比，但是沒有說清楚為什么。

思考

大家想一下，如果讓你來設計將一棵樹轉換為另一棵樹，你會怎么設計？

• 可能是直接暴力的根據index遍歷比較，相同保留，不同就替換？

• 也可能是用動態規劃計算新舊兩個節點變換所有情況的最小DOM操作次數？Min(新增，刪除，替換)

  等等，我相信還有很多種可能。

  第一種非常粗暴，第二種是假設所有操作的優先級是相同的。第二種方案也就是我們傳統的diff算法的核心方案，下面我們就此展開討論

首先思考一個問題，創建一顆樹的需要的復雜度是多少？

很簡單，因為樹是一種遞歸的數據結構，需要遞歸的創建，復雜度O(n)。但是DOM的操作是非常耗性能的！

再思考一下，將一棵樹轉換為另一顆樹，每個節點如何操作可以最少次數的操作DOM？

太抽象了想不清楚沒關系。下面我們來簡化一下問題。

思考一下，將一個字符串轉換為另一個字符串所需的最小操作次數，要如何計算？[wiki Edit distance][]

題目還是理解的不是很清晰？看下面的示例！[leetcode 72.編輯距離][leetcode 72.]

編輯距離

可能有部分同學已經想到了，直觀的方式是用動態規劃，通過這種記憶化搜索減少時間復雜度！

下面就展開介紹一下如何用動態規劃解這道題

代碼

/**
?*?@param?{string}?word1
?*?@param?{string}?word2
?*?@return?{number}
?*/
var?minDistance?=?function(word1,?word2)?{
??//1.初始化
??let?n?=?word1.length,?m?=?word2.length
??let?dp?=?new?Array(n+1).fill(0).map(()?=>?new?Array(m+1).fill(0))
??for?(let?i?=?0;?i?<=?n;?i++)?{
??????dp[i][0]?=?i
??}
??for?(let?j?=?0;?j?<=?m;?j++)?{
??????dp[0][j]?=?j
??}
??//2.dp
??for(let?i?=?0;?i?<=?n;?i++)?{
??????for(let?j?=?0;?j?<=?m;?j++)?{
??????????if(i*j)?{
??????????????dp[i][j]?=?word1[i-1]?==?word2[j-1]???dp[i-1][j-1]:?(Math.min(dp[i-1][j],?dp[i][j-1],?dp[i-1][j-1])?+?1)
??????????}?else?{
??????????????dp[i][j]?=?i?+?j
??????????}?console.log(dp[i][j])
??????}
??}
??return?dp[n][m]
};

得到字符串的最小編輯距離需要O(n^2)復雜度 -> 樹的最小編輯距離需要O(n^3)。

總結

以上是生活随笔為你收集整理的diff算法_传统Diff算法为什么时间复杂度要O(n ^3)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。