Estructuras de datos y algoritmos: Por qué una computadora más rápida no salva un mal algoritmo
Cómo la forma de organizar los datos decide qué es rápido: Big-O, tablas hash, árboles, montículos, ordenamiento, grafos, programación dinámica y decisiones voraces.
Prueba 3 preguntas
1. Un algoritmo O(n²) pasa a una computadora 1000 veces más rápida. En el mismo tiempo, ¿cuánto más grande puede ser la entrada?
- Unas 100 veces más grande
- Unas 1000 veces más grande
- Unas 32 veces más grande
Ver la respuesta
Respuesta: Unas 32 veces más grande
El tiempo crece con n al cuadrado, así que acelerar 1000 veces solo permite la raíz cuadrada de 1000, unas 32 veces más datos.
2. Duplicar el tamaño de la entrada de un algoritmo O(n log n), ¿qué le hace aproximadamente a su tiempo de ejecución?
- Lo duplica exactamente, no más
- Lo cuadruplica más o menos
- Lo duplica y un poco más
Ver la respuesta
Respuesta: Lo duplica y un poco más
n se duplica y log n solo crece un paso, así que el tiempo sube algo más del doble, mucho más suave que el crecimiento cuadrático.
3. ¿Qué ignora deliberadamente la notación Big-O?
- Los factores constantes y los términos menores
- Cómo crece el tiempo con la entrada
- Cómo se comporta el algoritmo en el peor caso
Ver la respuesta
Respuesta: Los factores constantes y los términos menores
Big-O describe el ritmo de crecimiento para entradas grandes, así que 3n² + 100n y n² son ambos O(n²).
El quiz completo llega antes de tus apps
BrainTok te hace unas preguntas como estas antes de abrir las apps que elijas, y tu tiempo de pantalla se vuelve aprendizaje. Para iPhone.
Únete a la beta