Si solo le dan un grupo de números, primero tendría que construir un bst.
Si el bst no está equilibrado, la inserción toma tiempo lineal (O (n)) en el peor de los casos. Entonces, insertar n números significaría (1 + 2 + 3 + 4 + ……. + N-1) operaciones que hacen que la complejidad O (n ^ 2).
Sin embargo, los árboles de búsqueda binarios equilibrados como el árbol rojo-negro o el árbol AVL que tienen un tiempo de inserción promedio de O (logn) pueden reducir bastante la complejidad. Entonces la inserción podría hacerse en O (nlogn). Pero en este caso, tendría que hacer los cambios necesarios en el código para garantizar que bst permanezca equilibrado.
- ¿Qué es un buen algoritmo para las respuestas de la prueba de personalidad?
- ¿Qué es la recurrencia en análisis de diseño y algoritmos?
- ¿Cuál es la forma más rápida (estructura de datos) para buscar la matriz multidimensional?
- ¿Podría dar un algoritmo que calcule la puntuación máxima de la mejor alineación de secuencia (S ', T') de S y T?
- ¿Cuáles son algunas buenas implementaciones de un algoritmo evolutivo / genético en C / C ++?
Luego, la siguiente tarea sería atravesar el árbol con O (n) complejidad.
Con cuál debe ir depende del rango de n. Si n toma valores pequeños, no hay una diferencia apreciable entre logn y n ^ 2. Pero en casos del mundo real donde n es bastante grande, es mejor usar un árbol de búsqueda binario equilibrado.
