Aquí está la pregunta publicada aquí hace años sobre una pregunta de entrevista en la que, dado un nodo de un árbol DOM, necesitamos encontrar el nodo en la misma posición desde un árbol DOM idéntico.
Aquí está la solución iterativa que se me ocurrió.
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; }Básicamente, solo camino hacia atrás desde el objetivo hasta la raíz, creando el camino inverso. La ruta inversa es una matriz donde cada elemento es el índice secundario de un nodo. Recorra la ruta desde rootB hasta el destino, extrayendo el siguiente índice hasta que la matriz de ruta esté vacía. Finalmente devolvemos el puntero al nodo de destino.
Mi pregunta es:
O(n) , siendo n el número de nodos DOM en el árbol DOM. Creo que sucede cuando tenemos dos listas vinculadas y el nodo de destino es el último nodo de cada lista vinculada. La parte de confusión para mí es que para cada nivel también estamos llamando a Array.prototype.indexOf para obtener el índice, y esto podría tomar hasta O(D) , siendo D el diámetro del árbol y para un nodo de hoja, tomará O((some-constant)n) para obtener el índice. , Más importante aún, ¿cuál es la complejidad de tiempo promedio ? Estamos atravesando un árbol dos veces. Parece que va a ser la altura o la profundidad del árbol. Si es un árbol completamente equilibrado, la altura del árbol será logN . ¿Eso significa que la complejidad de tiempo promedio es logN ? 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; } } ¿Cuál es la complejidad del tiempo en este caso? Aún peor caso O(n) y promedio/mejor caso O(logN) . ¿Es este enfoque recursivo mejor que el enfoque iterativo en términos de complejidad de tiempo ya que no necesitaríamos hacer indexOf para cada nivel?
¿Cuál es la complejidad de tiempo (promedio) para esta solución?
Es O(min(d.logn, n)) donde d es el factor de ramificación (máximo) de los nodos (2 para árboles binarios). La llamada indexOf es responsable de este coeficiente. Sin embargo, incluso si d es grande, los nodos que se escanean durante indexOf nunca se vuelven a visitar, por lo que la complejidad del tiempo también es O(n) (como límite superior). Para d relativamente más pequeño (en comparación con n ), O(d.logn) expresa mejor la complejidad del tiempo. Para cubrir ambos extremos podemos decir: O(min(d.logn, n)). Esto expresa el hecho de que si d tiende a n , necesariamente logn se vuelve pequeño (la altura del árbol disminuye).
El peor de los casos es fácil, ya que necesitamos visitar cada nodo una vez, por lo que será O(n), siendo n el número de nodos DOM en el árbol DOM. Creo que sucede cuando tenemos dos listas vinculadas y el nodo de destino es el último nodo de cada lista vinculada.
Verdadero.
La parte de confusión para mí es que para cada nivel también estamos llamando a
Array.prototype.indexOfpara obtener el índice, y esto podría tomar hasta O (D), siendo D el diámetro del árbol y para un nodo de hoja tomará O((alguna-constante)n) para obtener el índice.
El diámetro no se trata aquí. La complejidad de indexOf depende del número de hermanos . En el caso de un árbol degenerado que realmente es una lista enlazada (como escribiste), D es 1, es decir, ninguno de los nodos tiene hermanos, por lo que siempre se llama a indexOf en una matriz con un solo elemento: indexOf toma un tiempo constante en Ese caso.
Estamos atravesando un árbol dos veces.
Un factor de 2 es irrelevante para derivar una complejidad de tiempo.
Parece que va a ser la altura o la profundidad del árbol. Si es un árbol completamente balanceado, la altura del árbol será logaritmo de N. ¿Eso significa que la complejidad de tiempo promedio es logN?
Sí. Incluso los árboles "casi" equilibrados, como los árboles AVL, los árboles rojo-negro, ... todavía le dan complejidad a este tiempo logarítmico. Si crea un árbol al azar, se espera que esté bastante equilibrado y su altura sea O (logN).
Si escribo la solución usando un enfoque DFS recursivo, donde recorremos ambos árboles simultáneamente, [...] ¿Cuál es la complejidad del tiempo en este caso?
Aquí no hace uso de los parent , por lo que, en el peor de los casos, es posible que deba visitar cada nodo. Esto lo convierte en O(n).
¿Es este enfoque recursivo mejor que el enfoque iterativo en términos de complejidad de tiempo ya que no necesitaríamos hacer
indexOfpara cada nivel?
La estrategia indexOf no es tan mala si d es mucho menor que n . Sin embargo, si no tenemos idea de si ese es el caso, entonces la complejidad de tiempo en el peor de los casos es la misma: O (n).
Si d es mucho menor que n , entonces el primer algoritmo tiene una mejor complejidad de tiempo, O(d.logn).