19
¿Cuál es la complejidad del tiempo de cruce de árboles, estoy seguro de que debe ser obvio, pero mi pobre cerebro no puede resolverlo en este momento.¿Cuál es la complejidad del tiempo de cruce de árboles?
A
Respuesta
20
Depende del tipo de recorrido que esté realizando y del algoritmo, pero normalmente sería O (n) donde n es la cantidad total de nodos en el árbol. La implementación recursiva canónica de primer recorrido de profundidad consumirá memoria (en la pila) en el orden del nivel más profundo, que en un árbol equilibrado sería log (n).
+0
¿Es esto cierto para un árbol n-ary? Tengo una estructura de datos que es un árbol de máxima profundidad 4 y para atravesarlo, mi amigo está usando 3 para bucles, y está diciendo que su algoritmo se ejecuta en tiempo 'O (n^3) ', pero creo que se está ejecutando en' n' tiempo, 'n' es el número total de nodos en el árbol – Nicholas
+4
@Nocholas, está en lo correcto y su amigo está equivocado. Está en). – Uri
1
No que acaba de ser n de un árbol con n nodos?
Visitas cada árbol de permiso una vez, ¿no? Entonces diría que es lineal.
+0
Supongo que debería ser un árbol con "n nodos" y no "n hojas". – aamadmi
+0
Tienes razón, terminoligy equivocado :) – Nanne
+0
@Nanne Con el algoritmo correcto, de hecho es una complejidad lineal en el tiempo (visitando cada nodo una vez), pero aún no puede tener una complejidad lineal en el espacio. Como usar la pila. – Tim
Cuestiones relacionadas
- 1. ¿Cuál es la complejidad de tiempo del método java.util.Collections.sort()?
- 2. ¿Cuál es la complejidad de tiempo de LinkedList.getLast() en Java?
- 3. ¿Cuál es la complejidad de tiempo de .NET list.sort()
- 4. ¿Cuál es la complejidad de tiempo de HashMap.containsKey() en java?
- 5. ¿Cuál es la complejidad de tiempo de HTML DOM búsquedas
- 6. Complejidad del tiempo de la tabla hash
- 7. ¿Cuál es la complejidad del tiempo de ejecución de las funciones de la lista de python?
- 8. Complejidad del tiempo del algoritmo de Euclides
- 9. Complejidad del tiempo de la potencia()
- 10. ¿Cuál es la complejidad del tiempo de indexación, inserción y eliminación de estructuras de datos comunes?
- 11. ¿Cuál es la complejidad del tiempo para hacer estallar elementos de la lista en Python?
- 12. TreeMap - Complejidad del tiempo de búsqueda
- 13. Complejidad del tiempo del algoritmo de Prim
- 14. ¿Cuál es la complejidad del tiempo de iteración a través de un estándar :: set/std :: map?
- 15. ¿Cuál es la complejidad del tiempo de ejecución de una instrucción switch?
- 16. Complejidad del tiempo de consulta SQL
- 17. Gallop ¿Complejidad del tiempo de búsqueda?
- 18. Complejidad del tiempo del algoritmo de Fleury
- 19. ¿La complejidad del tiempo de las operaciones del conjunto python?
- 20. ¿Cuál es la complejidad de OrderedDictionary?
- 21. Complejidad del tiempo del conjunto en Java
- 22. Analizando algoritmos para la complejidad del tiempo
- 23. ¿Cuál es la complejidad de concatenación de cuerdas balanceadas?
- 24. analizando la complejidad del tiempo de mis programas
- 25. Complejidad del tiempo para java ArrayList
- 26. Complejidad de tiempo
- 27. Complejidad del tiempo de un algoritmo recursivo
- 28. ¿Cuál es la complejidad del tiempo A * y cómo se deriva?
- 29. Complejidad del tiempo de consulta de la base de datos
- 30. ¿Cuál es la complejidad de tiempo de la función de conteo en clojure?
Es lineal Art of Programming Vol 1 página 326 – new299
¿Ese es el arte de la programación de Knuth? Intento encontrar esto para darle a un amigo un buen ejemplo de que para un árbol n-ary es lineal. – Nicholas
sí Knuth's "El arte de la programación de computadoras" – new299