Complejidad del algoritmo y notación Big O

Analicemos la complejidad de los algoritmos y, en particular, cómo la medimos en el contexto de los algoritmos.

Diferentes algoritmos, dado el mismo problema que resolver y las mismas entradas, toman un tiempo diferente para resolver el problema.

A veces, un momento muy diferente, especialmente a medida que aumenta la cantidad de elementos que necesitan administrar.

Esta complejidad se llamaO grande, por ninguna otra razón que usemos mayúsculasocarta como convención:O(n),O(1)etcétera.

Las medidas más populares de Big O que verá, ordenadas de más eficiente a menos eficiente, son:

  • O(1)
  • O(log n)
  • O(n)
  • O(n * log n)
  • O(n^2)
  • O(n!)

dóndenes el número de entradas. Por ejemplo, si necesita ordenar 2 elementosnes 2, y si necesita ordenar 20.000 elementos,nes 20.000.

Pero no es necesario sustituir el valor en elO()cálculo. Ese es un símbolo, destinado a señalar a los desarrolladores y a todos los que miran los algoritmos su eficiencia.

Un algoritmo conO(1)la eficiencia es la mejor posible que podemos encontrar. El tiempo para ejecutar no depende de la cantidad de entradas, siempre toma el mismo tiempo para ejecutarse

Un algoritmo conO(n)escamaslinealmentecon el número de entradas. Si con 10 elementos tarda 1 segundo, con 100 elementos tardará 10 segundos.

Un algoritmo conO(n^2), si con 4 elementos tarda 16 segundos, con 10 elementos tarda 100 segundos.

Analizaremos y calcularemos la eficiencia Big O de un buen número de algoritmos en las próximas lecciones.

Es importante tener en cuenta que la notación Big O no nos da toda la información que necesitamos para juzgar si un algoritmo será más rápido que otro, en particular si su valor Big O es el mismo. En este caso, deberá utilizar otras herramientas para probar la eficiencia.

Pero cuando los algoritmos tienen diferentes clases (O(n)vsO(n^2)por ejemplo), no hay duda.