這里是多年前在這里發布的問題，關于一道面試題，給定DOM樹中的一個節點，我們需要從一個相同的DOM樹中找到相同位置的節點。
這里是我想到的一個迭代解決方案
。下面是我想出的一個迭代解決方案
const findCorrespondingNode = （rootA, rootB, nodeA）=> {
let currentNode = nodeA;
const path = [];
while (currentNode !== rootA) {
const index = Array. prototype.indexOf.call(
currentNode.parentElement.children,
當前節點
);
path.push（index）。
currentNode = currentNode.parentElement。
}
currentNode = rootB;
while (path.length) {
currentNode = currentNode.children[path.pop() ] 。
}
return currentNode;
}
基本上，我只是從目標向后走到根，創建反向路徑。反向路徑是一個陣列，每個元素都是一個節點的子索引。 沿著路徑從根B到目標，跳出下一個索引，直到路徑陣列為空。最后我們回傳到目標節點的指標。
我的問題是：
- 這個解決方案的（平均）時間復雜性是多少？更糟糕的情況是很容易的，因為我們需要訪問每個節點一次，所以它將是
O(n)，n是DOM樹中DOM節點的數量。我認為這發生在我們有兩個鏈接串列，而目標節點是每個鏈接串列中的最后一個節點。我感到困惑的部分是，對于每一層，我們也在呼叫Array.prototype.indexOf來獲得索引，這可能需要O(D)，D是樹的直徑，對于一個葉子節點，這將需要O((某常數)n)來獲得索引。, 更重要的是，平均時間復雜性是多少？我們正在對一棵樹進行兩次遍歷。看起來，這將是樹的高度或深度。如果它是一棵完全平衡的樹，樹的高度將是logN。這是否意味著平均時間復雜度是logN？ - 如果我使用遞回DFS方法撰寫解決方案，我們同時遍歷兩棵樹，即
const findCorrespondingNode = （rootA, rootB, target）=> {
if(rootA == target) {
return rootB;
}
for (let i = 0; i < rootA.children.length; i ) {
const foundNode = findCorrespondingNode(rootA.children[i], rootB.children[i], target) 。
if(foundNode) return foundNode;
}
這種情況下的時間復雜性是多少？仍然是較差的情況O(n)和平均/最佳的情況O(logN)。這種遞回方法在時間復雜度上是否比迭代方法更好，因為我們不需要為每一層做indexOf？
uj5u.com熱心網友回復：
這個解決方案的（平均）時間復雜性是多少？
它是O(min(d.logn, n))，其中d是節點的（最大）分支因子（二叉樹為2）。indexOf呼叫負責這個系數。然而，即使d很大，在indexOf程序中掃描的節點也不會被再次訪問，所以時間復雜度也是O(n)（作為一個上界）。對于相對較小的d（與n相比），O(d.logn)更好地表達了時間復雜性。為了涵蓋這兩個極端，我們可以說。O(min(d.logn, n))。這表達了這樣一個事實：如果d接近n，那么必然logn變得很小（樹的高度減少了）。
更糟糕的情況很簡單，因為我們需要訪問每個節點一次，所以它將是 O(n)，n 是 DOM 樹中的 DOM 節點數量。我認為當我們有兩個鏈接串列并且目標節點是每個鏈接串列中的最后一個節點時，就會發生這種情況。
真。
對我來說，困惑的部分是，對于每一層，我們也在呼叫
Array.prototype.indexOf來獲取索引，這可能需要花費 O(D)，D 是樹的直徑，對于一個葉子節點，它將需要 O((某常數)n) 來獲取索引。
這里不關心直徑。indexOf的復雜性取決于siblings的數量。在一個真正是鏈接串列的退化樹的情況下（如你所寫），D是1，即沒有一個節點有兄弟姐妹，所以indexOf總是在一個只有一個元素的陣列上被呼叫。indexOf在這種情況下需要恒定的時間。
我們正在對一棵樹進行兩次遍歷。
2的系數對于推匯出時間復雜度是不相關的。
這似乎是樹的高度或深度的問題。如果它是一棵完全平衡的樹，樹的高度將是 logN。這是否意味著平均時間復雜度是 logN？
是的。即使是 "幾乎 "平衡的樹，如 AVL 樹、紅黑樹......也會產生這種對數時間復雜度。如果你隨機創建一棵樹，預計它將是相當平衡的，而且它的高度是O(logN)。
如果我使用遞回DFS方法撰寫解決方案，我們同時遍歷兩棵樹，[...]這種情況下的時間復雜性是多少？在這里，你沒有利用
parent鏈接，因此在最壞的情況下，你可能不得不訪問每個節點。這使得它變成了 O(n)。就時間復雜性而言，這種遞回方法是否比迭代方法更好，因為我們不需要為每一層做
indexOf？
如果d比n小得多，那么indexOf策略也不是那么糟糕。然而，如果我們完全不知道情況是否如此，那么最壞情況下的時間復雜度是一樣的 - O(n)。
如果d遠小于n，那么第一種演算法的時間復雜度更好，為O(d.logn)。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/308845.html
標籤：