La notación Big O es una forma de describir la velocidad o complejidad de un algoritmo dado. Si su proyecto actual exige un algoritmo predefinido, es importante comprender qué tan rápido o lento es en comparación con otras opciones.
¿Qué es la notación Big O y cómo funciona?
En pocas palabras, la notación Big O le dice la cantidad de operaciones que realizará un algoritmo. Recibe su nombre del literal "Big O" delante del número estimado de operaciones.
Lo que la notación Big O no te dice es la velocidad del algoritmo en segundos. Hay demasiados factores que influyen en el tiempo que tarda en ejecutarse un algoritmo. En su lugar, usará la notación Big O para comparar diferentes algoritmos por la cantidad de operaciones que realizan.
Big O establece un tiempo de ejecución en el peor de los casos
Imagina que eres un maestro con una estudiante llamada Jane. Desea encontrar sus registros, por lo que utiliza un algoritmo de búsqueda simple para revisar la base de datos de su distrito escolar.
Sabes que la búsqueda simple tarda O (n) veces en ejecutarse. Esto significa que, en el peor de los casos, tendrá que buscar en todos los registros (representados por n) para encontrar el de Jane.
Pero cuando ejecuta la búsqueda simple, encuentra que los registros de Jane son la primera entrada en la base de datos. No tiene que mirar todas las entradas, las encontró en su primer intento.
¿Este algoritmo tomó O (n) tiempo? ¿O tomó O (1) tiempo porque encontró los registros de Jane en el primer intento?
En este caso, 0 (1) es el mejor de los casos: tuvo suerte de que los registros de Jane estuvieran en la parte superior. Pero la notación Big O se centra en el peor de los casos, que es 0 (n) para una búsqueda simple. Es una garantía de que la búsqueda simple nunca será más lenta que el tiempo O (n).
Los tiempos de ejecución del algoritmo crecen a diferentes velocidades
Suponga que se necesita 1 milisegundo para verificar cada elemento en la base de datos del distrito escolar.
Con una búsqueda simple, si tiene que verificar 10 entradas, tardará 10 ms en ejecutarse. Pero con el algoritmo de búsqueda binaria , solo tiene que verificar 3 elementos, lo que demora 3 ms en ejecutarse.
En la mayoría de los casos, la lista o base de datos que necesita buscar tendrá cientos o miles de elementos.
Si hay mil millones de elementos, el uso de una búsqueda simple tomará hasta mil millones de ms, u 11 días. Por otro lado, usar la búsqueda binaria tomará solo 32 ms en el peor de los casos:
Claramente, los tiempos de ejecución para la búsqueda simple y la búsqueda binaria no crecen casi al mismo ritmo. A medida que la lista de entradas aumenta, la búsqueda binaria tarda un poco más en ejecutarse. El tiempo de ejecución de la búsqueda simple crece exponencialmente a medida que aumenta la lista de entradas.
Por eso es tan importante saber cómo aumenta el tiempo de ejecución en relación con el tamaño de una lista. Y aquí es exactamente donde la notación Big O es tan útil.
La notación Big O muestra el número de operaciones
Como se mencionó anteriormente, la notación Big O no muestra el tiempo que se ejecutará un algoritmo. En cambio, muestra el número de operaciones que realizará. Le dice qué tan rápido crece un algoritmo y le permite compararlo con otros.
A continuación, se muestran algunos algoritmos comunes y sus tiempos de ejecución en notación Big O:
| Notación Big O | Algoritmo de ejemplo |
|---|---|
| O (log n) | Búsqueda binaria |
| En) | Búsqueda simple |
| O (n * log n) | Ordenación rápida |
| En 2) | Orden de selección |
| ¡En!) | Vendedor ambulante |
Ahora sabes lo suficiente como para ser peligroso con la notación Big O. Sal y comienza a comparar algoritmos.