Notación Big O: conceptos básicos

2.1 Definición de la notación Big O.

La notación Big O es una notación matemática que se utiliza para describir el límite superior del tiempo de ejecución o el consumo de recursos de un algoritmo en función del tamaño de los datos de entrada. Ayuda a determinar cómo bien escala un algoritmo y cómo cambia su rendimiento al aumentar el volumen de datos.

La notación Big O se centra en los aspectos más significativos del algoritmo, ignorando las constantes y términos menos significativos, lo que permite centrarse en el comportamiento a largo plazo del algoritmo.

Notaciones principales:

O(1) — Complejidad constante:

• El tiempo de ejecución del algoritmo no depende del tamaño de los datos de entrada.
• Ejemplo: acceso a un elemento de un array por su índice.

O(n) — Complejidad lineal:

• El tiempo de ejecución del algoritmo depende linealmente del tamaño de los datos de entrada.
• Ejemplo: recorrido simple de todos los elementos de un array.

O(log n) — Complejidad logarítmica:

• El tiempo de ejecución del algoritmo crece logarítmicamente con el tamaño de los datos de entrada.
• Ejemplo: búsqueda binaria en un array ordenado.

O(n^2) — Complejidad cuadrática:

• El tiempo de ejecución del algoritmo depende cuadráticamente del tamaño de los datos de entrada.
• Ejemplo: ordenamiento por burbuja, ordenamiento por inserción.

O(2^n) — Complejidad exponencial:

• El tiempo de ejecución del algoritmo depende exponencialmente del tamaño de los datos de entrada.
• Ejemplo: resolución del problema de la mochila mediante fuerza bruta.

2.2 Interpretación de la notación Big O.

¿Cómo interpretar y usar la notación Big O?

Ignorar constantes y términos menos significativos:

Big O describe el orden de crecimiento de una función, ignorando constantes y términos menos significativos. Por ejemplo, O(2n) y O(3n) se interpretan como O(n).

Comparación de algoritmos:

Big O permite comparar algoritmos según su eficiencia asintótica. Por ejemplo, un algoritmo con O(n log n) es más eficiente que uno con O(n^2) para volúmenes de datos muy grandes.

Análisis del peor caso:

Big O se usa generalmente para analizar el peor caso del tiempo de ejecución de un algoritmo, lo que permite estimar su complejidad máxima.

Ignorar constantes.

Ignorar constantes y términos menos significativos

Ejemplo 1:

Consideremos dos funciones:

• f(n) = 3n + 2
• g(n) = 5n + 1

Ambas funciones tienen complejidad lineal, ya que el término dominante en cada función es n. Por lo tanto, ambas funciones se interpretan como O(n), a pesar de las diferencias en los coeficientes y términos adicionales.

Ejemplo 2:

Consideremos dos funciones:

• f(n) = n^2 + 3n + 4
• g(n) = 2n^2 + n

Ambas funciones tienen complejidad cuadrática, ya que el término dominante es n^2. Ambas expresiones se interpretan como O(n^2), a pesar de las diferencias en los demás términos y coeficientes.

2.3. Comparación de algoritmos

1. Comparación de algoritmos con volúmenes de datos muy grandes

Ejemplo 1:

• El algoritmo A tiene una complejidad temporal de O(n^2).
• El algoritmo B tiene una complejidad temporal de O(n log n).

Para valores pequeños de n, el algoritmo A puede ser más rápido por tener constantes más pequeñas, pero para valores grandes de n, el algoritmo B será significativamente más rápido, ya que su crecimiento es logarítmico y no cuadrático.

Ejemplo 2:

• El algoritmo X tiene una complejidad temporal de O(n).
• El algoritmo Y tiene una complejidad temporal de O(1).

El algoritmo Y siempre será más rápido, independientemente del tamaño de n, ya que O(1) significa que el tiempo de ejecución del algoritmo no depende del tamaño de los datos de entrada.

2. Análisis del peor caso

Ejemplo 1:

El algoritmo de ordenamiento por burbuja tiene una complejidad temporal de O(n^2) en el peor caso, cuando el array está ordenado en orden inverso. Esto significa que para cada elemento en el array se requerirá comparación y posiblemente intercambio con cada otro elemento.

Ejemplo 2:

La búsqueda binaria tiene una complejidad temporal de O(log n) en el peor caso. Esto significa que incluso en el peor caso, el número de pasos necesarios para encontrar un elemento dependerá logarítmicamente del tamaño del array, lo cual es muy eficiente.

3. Impacto en el rendimiento y la escalabilidad

Ejemplo 1:

Si tenemos dos algoritmos para procesar datos, uno con una complejidad temporal de O(n^2) y otro con O(n log n), y aumentamos el tamaño de los datos de 1000 elementos a 10,000 elementos, la diferencia en el rendimiento será claramente notable.

• El algoritmo con O(n^2) realizará aproximadamente 100,000,000 operaciones para 10,000 elementos.
• El algoritmo con O(n log n) realizará alrededor de 40,000 operaciones para 10,000 elementos.

Ejemplo 2:

Consideremos un algoritmo que funciona con O(2^n). Si aumentamos el tamaño de los datos de entrada de 10 a 20 elementos, el número de operaciones aumenta exponencialmente.

• Para n = 10: 2^10 = 1024 operaciones.
• Para n = 20: 2^20 = 1,048,576 operaciones.

Esto muestra lo rápido que la complejidad exponencial se vuelve impracticable para valores grandes de n.