Notación Big O

11.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 consumo de recursos de un algoritmo dependiendo del tamaño de los datos de entrada. Ayuda a determinar cómo bien se escala un algoritmo y cómo su rendimiento cambia con el aumento de datos.

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

Principales notaciones:

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 í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 aumento del 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 de 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: solución del problema de la mochila por enumeración completa.

Nota. Aprenderás más sobre búsqueda binaria, ordenamiento de burbuja y el "problema de la mochila" en las próximas lecciones.

11.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 por 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 suele utilizarse para analizar el peor caso del tiempo de ejecución de un algoritmo, lo que permite evaluar su complejidad máxima.

Ignorar constantes

Observemos ejemplos de 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 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 otros términos y coeficientes.

11.3. Comparación de algoritmos

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

Ejemplo 1:

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

Para valores pequeños de n, el algoritmo A puede ser más rápido debido a constantes menores, 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 complejidad temporal O(n).
• El algoritmo Y tiene complejidad temporal 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 de burbuja tiene complejidad temporal 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 necesitará comparar y posiblemente intercambiar con cada otro elemento.

Ejemplo 2:

La búsqueda binaria tiene complejidad temporal 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 escalabilidad

Ejemplo 1:

Si tenemos dos algoritmos para procesar datos, uno con complejidad temporal 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 rendimiento será 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 en O(2^n). Si aumentamos el tamaño de los datos de entrada de 10 a 20 elementos, el número de operaciones crece exponencialmente.

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

Esto muestra qué tan rápido la complejidad exponencial se vuelve impráctica para valores grandes de n.

1

Опрос

Estructuras de datos,  52 уровень,  4 лекция

недоступен

Estructuras de datos

Estructuras de datos

Открыть