Comenzando con big-o

¿Qué es la notación Big-O?

La notación Big-O es una notación que se usa para hablar sobre las tasas de crecimiento a largo plazo de las funciones. A menudo se usa en el análisis de algoritmos para hablar sobre el tiempo de ejecución de un algoritmo o conceptos relacionados como la complejidad del espacio.

En el uso común, la notación O grande se usa para hablar sobre cómo el tiempo de ejecución de un algoritmo se escala según el tamaño de la entrada. Por ejemplo, diríamos que la ordenación por selección tiene un tiempo de ejecución de O(n2) porque el tiempo de ejecución crece cuadráticamente en función del tamaño de la matriz a ordenar. Es decir, si duplica el tamaño de la entrada, el tiempo de ejecución de la ordenación por selección debería duplicarse aproximadamente. Cuando se usa la notación O grande, la convención es eliminar los coeficientes e ignorar los términos de orden inferior. Por ejemplo, aunque técnicamente no está mal decir que la búsqueda binaria se ejecuta en el tiempo O(2 log2 n + 17), se considera un estilo pobre y sería mejor escribir que la búsqueda binaria se ejecuta en tiempo O(log n).

Formalmente, la notación O grande se usa para cuantificar el comportamiento a largo plazo de una función. Decimos que f(n) = O(g) (a veces denotado f(n) ∈ O(g(n)) en algunas fuentes) si hay constantes fijas c y n0 tales que f(n) ≤ c · g(n) para todo n ≥ n0. Esta definición formal explica por qué no nos importan los términos de bajo orden (se pueden subsumir haciendo c más grande y aumentando n0) y los factores constantes (el término c los absorbe). Esta definición formal se usa a menudo en el análisis riguroso de algoritmos, pero rara vez se usa coloquialmente.

Calculando Big-O para tu código

Una forma de calcular el valor Big-O de un procedimiento que ha escrito es determinar qué línea de código se ejecuta más veces en su función, dado el tamaño de entrada n. Una vez que tenga ese número, elimine todos los términos excepto los de más rápido crecimiento y deshágase de los coeficientes: esa es la notación Big-O de su función.

Por ejemplo, en esta función, cada línea se ejecuta exactamente una vez y durante la misma cantidad de tiempo, independientemente del tamaño de a:

int first(int[] a){
   printf("Returning the first element of a");
   return a[0];
}

La función en sí podría tardar 1 milisegundo ((1 ms) * n0) o 100 milisegundos ((100 ms) * n0); el valor exacto dependería de la potencia de la computadora involucrada y en qué printf() está imprimiendo. Pero debido a que esos factores no cambian con el tamaño de a, no importan para los cálculos de Big-O: son coeficientes constantes, que eliminamos. Por lo tanto, esta función tiene un valor Big-O de O(1).

En esta función, la línea 3 (sum += a[i];) se ejecuta una vez para cada elemento en a, para un total de a.length (o n) veces:

int sum(int[] a){
   int sum = 0;
   for (int i = 0; i < a.length; i++){
        sum += a[i];
   }
   return sum;
}

Las sentencias i++ e i < a.length también se ejecutan cada una n veces; podríamos haber seleccionado esas líneas, pero no es necesario. Además, int sum = 0;, int i = 0 y return sum; cada uno se ejecuta una vez, que es menos de n veces; ignoramos esas líneas. No importa cuánto tiempo se tarde en ejecutar sum += a[i], ese es un coeficiente que depende de la potencia de la computadora, por lo que eliminamos ese coeficiente. Por lo tanto, esta función es O(n).

Si hay varias rutas de código, Big-O generalmente se calcula a partir del peor de los casos. Por ejemplo, a pesar de que esta función puede salir de inmediato sin importar qué tan grande sea a (si a[0] es 0), aún existe un caso que hace que la línea 6 ejecute a.length veces, entonces sigue siendo O(n):

int product(int[] a){
    int product = 0;
    for (int i = 0; i < a.length; i++){
        if (a[i] == 0)
            return 0;
        else 
            product *= a[i];
    }
    return product;
}