Notación Big O - Explicación simple con ilustraciones y video

La notación Big O se usa para comunicar qué tan rápido es un algoritmo. ¡Esto puede ser importante al evaluar los algoritmos de otras personas y al evaluar los suyos! En este artículo, explicaré qué es la notación Big O y le daré una lista de los tiempos de ejecución más comunes para los algoritmos que la usan.

Los tiempos de ejecución del algoritmo crecen a diferentes velocidades

Mi hijo Judah tiene muchos juguetes. De hecho, ¡ha adquirido mil millones de juguetes! Te sorprendería lo rápido que un niño puede conseguir tantos juguetes si es el primer nieto de ambos lados de la familia. ??

De todos modos, Judah tiene un problema. Cuando sus amigos lo visitan y quieren jugar con un juguete específico, puede llevar SIEMPRE encontrar el juguete. Por eso quiere crear un algoritmo de búsqueda que le ayude a encontrar un juguete específico lo más rápido posible. Está tratando de decidir entre dos algoritmos de búsqueda diferentes: búsqueda simple y búsqueda binaria. (No se preocupe si no está familiarizado con estos algoritmos).

El algoritmo elegido debe ser rápido y correcto. Por un lado, la búsqueda binaria es más rápida. Y Judah a menudo solo tiene unos 30 segundos antes de que su amigo se aburra buscando un juguete. Por otro lado, un algoritmo de búsqueda simple es más fácil de escribir y hay menos posibilidades de que se introduzcan errores. ¡Seguro que sería vergonzoso que su amigo encontrara errores en su código! Para tener mucho cuidado, Judah decide sincronizar ambos algoritmos con una lista de 100 juguetes.

Supongamos que se tarda 1 milisegundo en comprobar un juguete. Con una búsqueda simple, Judah tiene que revisar 100 juguetes, por lo que la búsqueda tarda 100 ms en ejecutarse. Por otro lado, solo tiene que verificar 7 juguetes con búsqueda binaria (log2 100 es aproximadamente 7, no se preocupe si esta matemática es confusa, ya que no es el punto principal de este artículo), por lo que la búsqueda demora 7 ms correr. Pero realmente, la lista tendrá mil millones de juguetes. Si es así, ¿cuánto tiempo llevará la búsqueda simple? ¿Cuánto tiempo llevará la búsqueda binaria?

Tiempo de ejecución para búsqueda simple versus búsqueda binaria, con una lista de 100 elementos

Judah ejecuta una búsqueda binaria con mil millones de juguetes y toma 30 ms (log2 1,000,000,000 es aproximadamente 30). "¡32 ms!" él piensa. “La búsqueda binaria es aproximadamente 15 veces más rápida que la búsqueda simple, porque la búsqueda simple tomó 100 ms con 100 elementos y la búsqueda binaria tomó 7 ms. Entonces, una búsqueda simple tomará 30 × 15 = 450 ms, ¿verdad? Mucho menos de los 30 segundos que le toma a mi amigo aburrirse ". Judá decide ir con una simple búsqueda. ¿Es esa la elección correcta?

No. Resulta que Judah estaba equivocado y perdió a un amigo de por vida. ? El tiempo de ejecución para una búsqueda simple con mil millones de elementos será de mil millones de ms, que son 11 días. El problema es que los tiempos de ejecución de la búsqueda binaria y la búsqueda simple no crecen al mismo ritmo.

¡Los tiempos de ejecución aumentan a velocidades muy diferentes! A medida que aumenta el número de elementos, la búsqueda binaria tarda un poco más en ejecutarse, pero la búsqueda simple tarda mucho más en ejecutarse. Entonces, a medida que la lista de números aumenta, la búsqueda binaria de repente se vuelve mucho más rápida que la búsqueda simple.

Así que Judah se equivocó al decir que la búsqueda binaria siempre es 15 veces más rápida que la búsqueda simple. Si hay mil millones de juguetes, es más como 33 millones de veces más rápido.

Es muy importante saber cómo aumenta el tiempo de ejecución a medida que aumenta el tamaño de la lista. Ahí es donde entra la notación Big O.

La notación Big O te dice qué tan rápido es un algoritmo. Por ejemplo, suponga que tiene una lista de tamaño n . La búsqueda simple necesita verificar cada elemento, por lo que tomará n operaciones. El tiempo de ejecución en notación Big O es O ( n ).

¿Dónde están los segundos? No hay ninguno: Big O no te dice la velocidad en segundos. La notación Big O le permite comparar el número de operaciones. Te dice qué tan rápido crece el algoritmo.

Hagamos otro ejemplo. La búsqueda binaria necesita operaciones log n para verificar una lista de tamaño n . ¿Cuál es el tiempo de ejecución en notación Big O? Es O (log n ). En general, la notación Big O se escribe de la siguiente manera.

Esto le dice el número de operaciones que realizará un algoritmo. Se llama notación Big O porque pones una "O grande" delante del número de operaciones.

Big O establece un tiempo de ejecución en el peor de los casos

Suponga que está utilizando una búsqueda simple para buscar un usuario en su base de datos de usuarios. Usted sabe que la búsqueda simple toma O ( n ) tiempo para ejecutarse, lo que significa que, en el peor de los casos, su algoritmo tendrá que buscar en todos los usuarios de la base de datos. En este caso, está buscando un usuario con el nombre 'aardvark213'. Este es el primer usuario de la lista. Por lo tanto, su algoritmo no tuvo que mirar todas las entradas, las encontró en el primer intento. ¿El algoritmo tomó O ( n ) tiempo? ¿O tomó O (1) tiempo porque encontró a la persona en el primer intento?

La búsqueda simple todavía lleva O ( n ) tiempo. En este caso, el algoritmo encontró lo que estaba buscando al instante. Ese es el mejor de los casos. Pero la notación Big O se trata del peor de los casos . Por lo tanto, puede decir que, en el peor de los casos , el algoritmo tendrá que examinar a todos los usuarios de la base de datos una vez. Eso es O ( n ) tiempo. Es una tranquilidad: sabes que la búsqueda simple nunca será más lenta que el tiempo O ( n ).

Algunos tiempos de ejecución comunes de Big O

Aquí hay cinco tiempos de ejecución de Big O que encontrará muchos, ordenados del más rápido al más lento:

  • O (log n ), también conocido como tiempo de registro. Ejemplo: búsqueda binaria.
  • O ( n ), también conocido como tiempo lineal . Ejemplo: búsqueda simple.
  • O ( n * log n ). Ejemplo: un algoritmo de clasificación rápido, como quicksort.
  • O ( n 2). Ejemplo: un algoritmo de clasificación lento, como la clasificación por selección.
  • Oh ( n !). Ejemplo: un algoritmo realmente lento, como el vendedor ambulante.

Visualización de diferentes tiempos de ejecución de Big O

Suponga que está dibujando una cuadrícula de 16 cuadros y puede elegir entre 5 algoritmos diferentes para hacerlo. Si utiliza el primer algoritmo, le llevará O (log n ) tiempo dibujar la cuadrícula. Puede realizar 10 operaciones por segundo. Con O (log n ) tiempo, le tomará 4 operaciones para dibujar una cuadrícula de 16 cajas (log 16 base 2 es 4). Por lo que le tomará 0,4 segundos dibujar la cuadrícula. ¿Qué pasa si tienes que dibujar 1.024 cajas? Le llevará registrar 1.024 = 10 operaciones, o 1 segundo para dibujar una cuadrícula de 1.024 cajas. Estos números utilizan el primer algoritmo.

El segundo algoritmo es más lento: lleva O ( n ) tiempo. Se necesitarán 16 operaciones para dibujar 16 cajas y 1,024 operaciones para dibujar 1,024 cajas. ¿Cuánto tiempo es eso en segundos?

A continuación, se indica cuánto tiempo llevaría dibujar una cuadrícula para el resto de los algoritmos, del más rápido al más lento:

También hay otros tiempos de ejecución, pero estos son los cinco más comunes.

Esta es una simplificación. En realidad, no se puede convertir de un tiempo de ejecución de Big O a una cantidad de operaciones tan ordenadamente, pero esta es una buena estimación.

Conclusión

Aquí están las principales conclusiones:

  • La velocidad del algoritmo no se mide en segundos, sino en el crecimiento del número de operaciones.
  • En cambio, hablamos de la rapidez con que aumenta el tiempo de ejecución de un algoritmo a medida que aumenta el tamaño de la entrada.
  • El tiempo de ejecución de los algoritmos se expresa en notación Big O.
  • O (log n ) es más rápido que O ( n ), pero se vuelve mucho más rápido a medida que crece la lista de elementos que está buscando.

Y aquí hay un video que cubre mucho de lo que se incluye en este artículo y más.

Espero que este artículo te haya aportado más claridad sobre la notación Big O. Este artículo se basa en una lección de mi curso en video de Manning Publications llamado Algorithms in Motion. El curso se basa en el asombroso libro Grokking Algorithms de Adit Bhargava. Él es quien dibujó todas las divertidas ilustraciones de este artículo.

Si aprende mejor a través de los libros, ¡obtenga el libro! Si aprende mejor a través de videos, considere comprar mi curso. Puede obtener un 39% de descuento en mi curso usando el código ' 39carnes '.