¿Qué es la Notación Big O?

¿Qué es la Notación Big O?

La notación Big O es una forma matemática de expresar el rendimiento de un algoritmo.

Por lo tanto, nos indica lo eficiente que es. Y de este modo, lo podemos comparar con otros.

Los miembros de "Los androides Premium" escuchan contenido adicional en audio sobre este artículo... ¡y otros 77 más!

Quiero más info

Hay que suscribirse para disfrutar de todo el contenido premium desde la web y la app, así como participar en las actividades premium: videoconferencias y canales premium en Discord.

Es una manera de poder expresar de manera abstracta, la capacidad de proceso que tiene un algoritmo. Y nos sirve para determinar si aumentando los valores de entrada, el algoritmo va a ser más o menos rápido.

Vamos a poner números y que esto quede más claro. 😉

  • Imagina un algoritmo al que si se le pasa 1 parámetro de entrada, tarda 1 segundo en devolver el resultado de salida
  • Si se le pasan 2 parámetros de entrada, tarda 2 segundos en completarse
  • Si se le pasan 3 parámetros de entrada, tarda 3 segundos en completarse

Sencillo, ¿verdad?

Pues esto sería una progresión aritmética. ✅


Vayamos ahora con otro algoritmo:

  • A este si se le pasa 1 parámetro de entrada, tarda 2 segundos en devolver el resultado de salida.
  • Pero… si se le pasan 2 parámetros de entrada, tarda 4 segundos en completarse
  • Y si se le pasan 4 parámetros de entrada, tarda 8 segundos en completarse

Esto ya no es lineal, ¿a qué no?

De hecho, se ve claro que la salida es el doble de la entrada.

Pues este algoritmo se correspondería con una progresión geométrica. ✅


Otro ejemplo más:

  • A este, si se le pasa 1 parámetro de entrada, tarda 1 segundo en completarse
  • Si se le pasan 2 parámetros de entrada, tarda 4 segundos en completarse
  • Si se le pasan 3 parámetros de entrada, tarda 9 segundos en completarse

Vemos que la salida es el cuadrado de la entrada.

La curva que se vería en la gráfica que saldría de aquí, sería más pronuncionada aún que la anterior.

Sería una progresión cuadrática. ✅


En el primer caso, la Big O sería O(n).

En el segundo, O(2 * n).

Y en el tercero, O(n2).

Ventajas

Lo bueno de la notaci’on Big O es que permite abstraernos de la máquina donde se está ejecutando. Por lo tanto, nos podemos centrar en lo eficiente que es el código en sí.

No queremos que si se corre el programa sobre una máquina más potente, el resultado sea diferente.

No sería no sería un método muy práctico de medida, ¿a qué no? 😊

Valores típicos

Algunos de los valores típicos de la Big O, suelen ser estos:

  • O(1) –> Tiempo constante
  • O(log n) –> Tiempo logarítmico
  • O(n) –> Tiempo lineal
  • O(n2) –> Tiempo cuadrático
  • O(n!) –> Tiempo factorial

Como habrás podido suponer, están ordenados de más eficiente a menos.

Curiosidad

La O viene de «Order».

Es decir, de clasificar el orden de magnitud de de la función a analizar.

Publicado: 2022-10-12 Actualizado: 2022-12-28

✉️ NEWSLETTER ANDROIDE ✉️

Deja tu email para recibir TIPS sobre ANDROID cada domingo GRATIS.

Además, AL APUNTARTE CONSEGUIRÁS el audio de 54 minutos con MI ESTRATEGIA para convertirte en un Desarrollador Android Senior DE REGALO. 🎁

Acepto que trates mis datos con privacidad.