¿Qué es la notación Big O?

La notación Big O (Big O) es una notación matemática utilizada para describir el comportamiento asintótico de una función y su límite superior. En el contexto del desarrollo de software, se aplica para evaluar el rendimiento de los algoritmos en términos de consumo de tiempo (complejidad temporal) y memoria (complejidad espacial) a medida que crece el tamaño de los datos de entrada. Describe el peor escenario de ejecución.

Las clases de complejidad temporal más comunes:

• O(1): Tiempo constante. El tiempo de ejecución no depende del tamaño de los datos de entrada.
• O(log n): Tiempo logarítmico. El tiempo de ejecución crece lentamente a medida que aumenta el tamaño de los datos de entrada (por ejemplo, búsqueda binaria).
• O(n): Tiempo lineal. El tiempo de ejecución es proporcional al tamaño de los datos de entrada (por ejemplo, búsqueda simple).
• O(n log n): Tiempo lineal-logarítmico. Común en algoritmos de ordenamiento eficientes (por ejemplo, ordenamiento rápido, ordenamiento por fusión).
• O(n^2): Tiempo cuadrático. El tiempo de ejecución crece proporcional al cuadrado del tamaño de los datos de entrada (por ejemplo, ordenamiento burbuja, ordenamiento por selección).
• O(2^n): Tiempo exponencial. El tiempo de ejecución crece muy rápidamente con el aumento del tamaño de los datos de entrada. Común en problemas de búsqueda exhaustiva.

Ejemplos de código y su complejidad temporal:

// O(1)
int primerElemento = array[0];

// O(n)
for (int i = 0; i < array.length; i++) {
    // alguna operación
}

// O(n^2)
for (int i = 0; i < array.length; i++) {
    for (int j = 0; j < array.length; j++) {
        // alguna operación
    }
}

La notación Big O se centra en el término dominante en la expresión e ignora las constantes y los términos menos significativos, ya que en entradas grandes su contribución se vuelve insignificante. Por ejemplo, un algoritmo con complejidad O(2n^2 + 5n + 10) se considera O(n^2).

Comprender Big O es importante para elegir los algoritmos y estructuras de datos más eficientes al desarrollar.