在相同的 DOM 树中找到相应的节点 - 平均和更差的时间复杂度是多少？

Question

Here is the question 几年前在这里发布了一个面试问题，给定 DOM 树中的一个节点，我们需要从相同的 DOM 树中找到相同位置的节点树.

这是我想出的迭代解决方案

const findCorrespondingNode = (rootA, rootB, nodeA) => {
  let currentNode = nodeA;
  const path = [];
  while (currentNode !== rootA) {
    const index = Array.prototype.indexOf.call(
      currentNode.parentElement.children,
      currentNode
    );
    path.push(index);
    currentNode = currentNode.parentElement;
  }
  currentNode = rootB;
  while (path.length) {
    currentNode = currentNode.children[path.pop()];
  }

  return currentNode;
}

基本上我只是从目标向后走到根，创建反向路径。反向路径是一个数组，其中每个元素都是节点的子索引。沿着从 rootB 到目标的路径行进，弹出下一个索引，直到路径数组为空。最后我们return指向目标节点的指针。

我的问题是：

这个解决方案的（平均）时间复杂度是多少？最坏的情况很容易，因为我们需要访问每个节点一次，所以它将是 O(n)，n 是 DOM 树中 DOM 个节点的数量。我认为当我们有两个链表并且目标节点是每个链表中的最后一个节点时会发生这种情况。 让我感到困惑的部分是对于每个级别我们也调用Array.prototype.indexOf来获取索引，这可能需要O(D)，D是树的直径，对于叶节点，它将需要 O((some-constant)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) 和 average/best 情况 O(logN)。就时间复杂度而言，这种递归方法是否比迭代方法更好，因为我们不需要为每个级别执行 indexOf？

Answer 1

what is the (average) time complexity for this solution?

它是 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变小（树的高度减小).

The worse case is easy since we need to visit each node once so it is going to be O(n), n being the number of DOM nodes in the DOM tree. I think it happens when we have two linked lists and the target node is the last node in each linked list.

正确。

The confusion part for me is that for each level we are also calling Array.prototype.indexOf to get the index, and this might take up to O(D), D being the tree's diameter and for a leaf node it is going to take O((some-constant)n) to get the index.

这里不关心直径。 indexOf 的复杂性取决于 兄弟姐妹 的数量。对于实际上是链表的退化树（如您所写），D 为 1，即 none 个节点有兄弟姐妹，因此 indexOf 总是在只有一个元素的数组上调用：indexOf 在这种情况下需要常数时间。

We are traversing a tree twice.

因子 2 与推导时间复杂度无关。

It seems like it is going to be the height or the depth of the tree. If it is a completely balanced tree, the height of the tree is going to be logN. Does that mean the average time complexity is logN?

是的。即使是“几乎”平衡的树，如 AVL 树、红黑树……仍然具有这种对数时间复杂度。如果随机创建一棵树，预计它会比较平衡，其高度为O(logN)。

If I write the solution using a recursive DFS approach, where we traverse both trees simultaneously, [...] What is the time complexity in this case?

这里你不使用parent链接，所以在最坏的情况下你可能不得不访问每个节点。这使得它 O(n).

Is this recursive approach better than the iterative approach in terms of time complexity since we wouldn't need to do indexOf for each level?

如果 d 比 n 小得多，indexOf 策略并没有那么糟糕。但是，如果我们根本不知道情况是否如此，那么最坏情况下的时间复杂度是相同的——O(n)。

如果d远小于n，那么第一种算法的时间复杂度更好，O(d.logn ).

在相同的 DOM 树中找到相应的节点 - 平均和更差的时间复杂度是多少？

Find corresponding node in an identical DOM tree - what is the average and worse time complexity?

javascript

algorithm

tree

dom