Notación Big O sin dolor: cómo medir tu código

La complejidad algorítmica es un tema fundamental en la programación, ya que nos permite medir la eficiencia de nuestros algoritmos y predecir su comportamiento a medida que el tamaño de la entrada aumenta. Una de las herramientas más importantes para medir la complejidad algorítmica es la notación Big O.

La notación Big O se utiliza para describir el comportamiento de un algoritmo en el peor de los casos. En otras palabras, nos dice cuánto tiempo tardará el algoritmo en ejecutarse en función del tamaño de la entrada. Por ejemplo, si un algoritmo tiene una complejidad de O(n), esto significa que el tiempo de ejecución aumentará linealmente con el tamaño de la entrada.

Tipos de complejidad

Hay varios tipos de complejidad algorítmica, pero aquí te presento algunos de los más comunes:

O(1): complejidad constante. El algoritmo tarda el mismo tiempo en ejecutarse independientemente del tamaño de la entrada.
O(log n): complejidad logarítmica. El algoritmo tarda un tiempo que aumenta logarítmicamente con el tamaño de la entrada.
O(n): complejidad lineal. El algoritmo tarda un tiempo que aumenta linealmente con el tamaño de la entrada.
O(n log n): complejidad lineal logarítmica. El algoritmo tarda un tiempo que aumenta linealmente con el tamaño de la entrada y también depende del logaritmo del tamaño de la entrada.
O(n^2): complejidad cuadrática. El algoritmo tarda un tiempo que aumenta cuadráticamente con el tamaño de la entrada.

Veamos un ejemplo de código para entender mejor la notación Big O. Supongamos que tenemos un arreglo de números y queremos encontrar el número más grande:

function encontrarMaximo(arr) {
    let maximo = arr[0];
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] > maximo) {
            maximo = arr[i];
        }
    }
    return maximo;
}

En este caso, el algoritmo tiene una complejidad de O(n), porque solo necesitamos recorrer el arreglo una vez para encontrar el número más grande.

Conclusión

La notación Big O es una herramienta fundamental para medir la complejidad algorítmica y predecir el comportamiento de nuestros algoritmos. Al entender la notación Big O, podemos escribir código más eficiente y escalable, lo que nos permitirá resolver problemas más complejos de manera más efectiva.