algorithm - preorden - ¿Cuál es la complejidad en el tiempo y el espacio de un recorrido de árboles primero en amplitud y primero en profundidad?
recorrido de un arbol matematicas discretas (3)
¿Puede alguien explicar con un ejemplo cómo podemos calcular la complejidad de tiempo y espacio de estos dos métodos de recorrido?
Además, ¿cómo la solución recursiva a la profundidad del primer recorrido afecta la complejidad del tiempo y el espacio?
DFS y complejidad del tiempo BFS: O (n)
Debido a que este es el recorrido del árbol, debemos tocar cada nodo, haciendo que este O (n) donde n sea el número de nodos en el árbol.
Complejidad del espacio BFS: O (n)
BFS deberá almacenar al menos un nivel completo del árbol en la cola ( implementación de la cola de muestra). Con un árbol binario totalmente equilibrado perfecto, esto sería (n / 2 + 1) nodos (el último nivel). Mejor caso (en este contexto), el árbol está muy desequilibrado y contiene solo 1 elemento en cada nivel y la complejidad del espacio es O (1). El peor de los casos sería almacenar (n - 1) nodos con un árbol N-ario bastante inútil en el que todos, excepto el nodo raíz, se encuentran en el segundo nivel.
DFS complejidad de espacio: O (d)
Independientemente de la implementación (recursiva o iterativa), la pila (implícita o explícita) contendrá d nodos, donde d es la profundidad máxima del árbol. Con un árbol equilibrado, esto sería (log n) nodos. El peor caso para DFS será el mejor caso para BFS, y el Mejor caso para DFS será el peor caso para BFS.
Hay dos factores principales de complejidad
- Complejidad del tiempo
- Complejidad del espacio
Complejidad del tiempo
Es la cantidad de tiempo necesaria para generar el nodo.
En DFS, la cantidad de tiempo necesaria es proporcional a la profundidad y al factor de ramificación. Para DFS, la cantidad total de tiempo necesaria es dada por:
1 + b + b2 + b3 + ... + bd ~~ bd
Así la complejidad del tiempo = O(bd)
Complejidad del espacio
Es la cantidad de espacio o memoria necesaria para obtener una solución. El DFS almacena solo la ruta actual que está siguiendo. De ahí que la complejidad del espacio sea una función lineal de la profundidad.
Entonces la complejidad del espacio está dada por O(d)
BFS:
La complejidad del tiempo es O(|V|) donde |V| es el número de nodos, necesita atravesar todos los nodos.
La integridad del espacio también es O(|V|) , ya que en el peor de los casos debe mantener todos los vértices en la cola.
DFS:
La complejidad del tiempo es nuevamente O(|V|) , necesita atravesar todos los nodos.
Complejidad del espacio: depende de la implementación, una implementación recursiva puede tener una complejidad de espacio O(h) [en el peor de los casos], donde h es la profundidad máxima de su árbol.
Usar una solución iterativa con una pila es en realidad lo mismo que BFS, solo usar una pila en lugar de una cola, por lo que obtiene tanto O(|V|) tiempo y complejidad de espacio.
(*) Tenga en cuenta que la complejidad del espacio y la complejidad del tiempo es un poco diferente para un árbol y para un gráfico general, ya que no es necesario mantener un conjunto visited para un árbol, y |E| = O(|V|) |E| = O(|V|) , entonces el |E| El factor es en realidad redundante.