La notación “Big O” se utiliza en programación para analizar el rendimiento o la complejidad de un algoritmo en cuanto al tiempo de ejecución. Es decir, Big O permite analizar cuánto tiempo tarda un algoritmo en ejecutarse en función del tamaño de la entrada.
Qué es "Big O"
Big O es una notación matemática inventada por los matemáticos alemanes Paul Bachmann y Edmund Landau, con el objetivo de clasificar algoritmos según su tiempo de ejecución.
Esta notación no se enfoca en tiempos exactos de ejecución, sino en cómo el tiempo de ejecución se comporta a medida que los datos crecen hacia el infinito. Este análisis ayuda a los desarrolladores a comparar y seleccionar algoritmos adecuados para resolver problemas de manera eficiente.
Las clasificaciones más comunes que recoge la notación Big O son:
- O(1): El tiempo de ejecución del algoritmo es constante y no depende del tamaño de la entrada.
- O(log N): El tiempo de ejecución del algoritmo crece de manera logarítmica en función del tamaño de la entrada.
- O(N): El tiempo de ejecución del algoritmo crece linealmente con el tamaño de la entrada. Es decir, si el tamaño de la entrada se duplica, el tiempo de ejecución también se duplica.
- O(N^2): El tiempo de ejecución del algoritmo crece cuadráticamente en función del tamaño de la entrada.
- O(2^N): El tiempo de ejecución crece de manera exponencial con el tamaño de la entrada.
Análisis de estructuras de datos
Las estructuras de datos son un componente fundamental en el diseño y análisis de algoritmos. La elección de la estructura de datos correcta puede influir en la eficiencia y la complejidad de un algoritmo, tanto en términos de tiempo como de espacio. Por lo tanto, es importante considerar cuidadosamente las estructuras de datos al diseñar algoritmos.
Al elegir una estructura de datos, debemos tener en cuenta su coste computacional al realizar operaciones como:
- Acceso
- Búsqueda
- Inserción
- Eliminación
Existen una serie de estructuras de datos que son comunes a la mayoría de lenguajes de programación y conviene conocer para determinar cual es el más adecuado en cada caso:
- Arrays: Almacena una colección de elementos accesibles a través de índices numéricos.
- Buscar dato: O(n)
- Añadir/Eliminar dato: O(n)
- Diccionarios hash: Almacena pares clave-valor y permite un acceso eficiente a los valores a través de una función de hash.
- Buscar dato: O(1)
- Añadir/Eliminar dato: O(1)
- Pilas de datos: Almacena datos en una estructura LIFO, de modo que el último dato almacenado es el primero en leerse.
- Buscar dato: O(n)
- Añadir/Eliminar dato: O(1)
- Colas de datos: Almacena datos en una estructura FIFO, de modo que el primer dato almacenado es el primero en leerse.
- Buscar dato: O(n)
- Añadir/Eliminar dato: O(1)
- Listas enlazadas: Lista flexible que almacena elementos con un valor y una referencia al siguiente elemento.
- Buscar dato: O(n)
- Añadir/Eliminar dato: O(1)
- Arboles equilibrados: Estructura jerárquica donde los elementos a la izquierda y derecha de la raíz se mantienen equilibrados.
- Buscar dato: O(log N)
- Añadir/Eliminar dato: O(log N)
El siguiente diagrama muestra en detalle la complejidad de las diferentes estructuras de datos existentes:
Análisis de algoritmos
A la hora de realizar el análisis de un algoritmo, debemos tratar de determinar el número de iteraciones que ejecutará nuestro código para un número de datos de entrada N:
- O(1): Solo se ejecuta una iteración.
- O(log N): En cada iteración, se descarta la mitad de los elementos.
- O(N): Se ejecutan tantas iteraciones como datos de entrada.
- O(N^2): Se ejecutan N*N iteraciones. (P.ej. Bucles anidados).
- O(2^N): Se ejecutan N^N iteraciones. (P.ej. Tantos bucles anidados como datos de entrada).
Las pautas principales que se deben tener en cuenta en el análisis son:
- Identificar los bucles y funciones recursivas, ya que son los elementos principales que se deben analizar.
- Identificar el coste de las operaciones realizadas dentro de los bucles.
- Asumir el peor caso.
- Simplificar la ecuación de coste.
Ejemplo:
Función a analizar:
/**
* Comprueba si uno de los dos datos
* dados ($e1 o $e2) existe en la lista indicada.
*/
function buscar(array $arr, int $e1, int $e2): bool
{
foreach ($arr as $valor) {
if ($valor === $e1) {
return true;
}
}
foreach ($arr as $valor) {
if ($valor === $e2) {
return true;
}
}
return false;
}Ejemplo de uso:
$miArray = [1, 2, 3, 4, 5];
$elem1 = 1;
$elem2 = 3;
if (buscar($miArray, $elem1, $elem2)) {
echo "Se ha encontrado alguno de los elementos.";
} else {
echo "No se han encontrado los elementos.";
}Calcular complejidad online
Existen herramientas online como TimeComplexity.ai que permiten determinar la complejidad de nuestro código en notación Big O.
Gracias a estos cálculos, podemos determinar si nuestro código es óptimo, escalable y sostenible. O, si por el contrario, es necesario realizar cambios en la forma de almacenar y procesar los datos para diseñar una solución más óptima.
