Tipos de Big-O en bucles

Tabla de Contenidos

O(1) – Constante

Aunque O(1) no suele estar asociado a bucles, es importante entender su existencia y cómo representa operaciones de tiempo constante. Por ejemplo:

public int obtenerPrimero(int[] array) {
    return array[0]; // O(1)
}Lenguaje del código: PHP (php)

Aquí, sin importar el tamaño del arreglo, acceder al primer elemento siempre tomaría la misma cantidad de tiempo, por lo que se considera O(1).

En el caso de un bucle con un número fijo de iteraciones, también puede entenderse como constante:

for (int i = 0; i < 10; i++) {...}

Dado que el número de iteraciones es siempre el mismo (10 en este ejemplo), el tiempo de ejecución no depende de un tamaño de entrada variable y puede clasificarse como O(1). No importa si n o cualquier otra variable cambia en el contexto general; el tiempo del bucle permanece constante, al igual que en el primer ejemplo: No importa cuantas veces lo ejecutemos siempre tendrá 10 iteraciones, por lo cual es O(1).

O(log n) – Logarítmica

Este se da en los casos donde el crecimiento es, por lo general, con potencias en cada iteración:

for(i=1; i<n; i*=2) {...}  // O(log n)Lenguaje del código: HTML, XML (xml)

Otro caso podría ser el siguiente:

for(i=n; i>=1; i/=2) {...}  // O(log n)Lenguaje del código: JavaScript (javascript)

Ejemplo: Búsqueda binaria en un array ordenado.

O(√n) – Raíz cuadrada

Hay algunos casos que se puede utilizar este tipo de big-O. Por ejemplo, para verificar el cálculo de valores primos.

for(i=0; i<Math.sqrt(n); i++) {...}  // O(√n)Lenguaje del código: JavaScript (javascript)

O(n) – Lineal

Este probablemente sea el caso más común de un bucle:

for(i=0; i<n; i++) {...}  // O(n)Lenguaje del código: JavaScript (javascript)

El big-O es el mismo si los pasos de un bucle cambian (siempre linealmente):

for(i=0; i<n; i+=2) {...}  // O(n/2) = O(n)

Incluso, si se tienen 3 bucles colocados de forma independiente:

for(i=0; i<n; i++){...}  // O(n)
for(i=0; i<m; i++){...}  // O(n+m)
for(i=0; i<p; i++){...}  // O(n+m+p)Lenguaje del código: JavaScript (javascript)

La complejidad total es O(n + m + p).

En caso de que los valores de n, m y p sean similares, se pueden aproximar al mayor de ellos, digamos que es n. Entonces, la expresión se puede reducir a algo similar a esto:

for(i=0; i<n; i++){...}  // O(n)
for(i=0; i<n; i++){...}  // O(n+n)
for(i=0; i<n; i++){...}  // O(n+n+n) = O(3n) = O(n)Lenguaje del código: JavaScript (javascript)

Ejemplo: Búsqueda lineal

O(n log n) – Linearítmica

La complejidad es mayor que lineal pero menor que cuadrática, común en algoritmos de ordenación eficientes.

Ejemplo: Implementación de Merge Sort.

public void mergeSort(int[] array, int inicio, int fin) {
    if (inicio < fin) {
        int mitad = (inicio + fin) / 2;
        mergeSort(array, inicio, mitad);
        mergeSort(array, mitad + 1, fin);
        merge(array, inicio, mitad, fin);
    }
}

private void merge(int[] array, int inicio, int mitad, int fin) {
    int n1 = mitad - inicio + 1;
    int n2 = fin - mitad;
    int[] izquierda = new int[n1];
    int[] derecha = new int[n2];
    System.arraycopy(array, inicio, izquierda, 0, n1);
    System.arraycopy(array, mitad + 1, derecha, 0, n2);
    int i = 0, j = 0, k = inicio;
    while (i < n1 && j < n2) {
        if (izquierda[i] <= derecha[j]) {
            array[k] = izquierda[i];
            i++;
        } else {
            array[k] = derecha[j];
            j++;
        }
        k++;
    }
    while (i < n1) {
        array[k] = izquierda[i];
        i++;
        k++;
    }
    while (j < n2) {
        array[k] = derecha[j];
        j++;
        k++;
    }
}Lenguaje del código: PHP (php)

O(n²) – Cuadrática

A continuación se puede observar un bucle anidado dentro de otro:

for(i=0; i<n; i++) {      
   for(j=0; j<m; j++) {}
}

En este caso, pueden darse dos situaciones:

Complejidad lineal: Si solo uno de los dos términos (ya sea n o m) crece mientras el otro se mantiene constante, la complejidad se puede considerar como O(n) o O(m), según cuál de ellos crezca.
Complejidad cuadrática: En el caso más usual, cuando tanto n como m crecen de manera proporcional, la complejidad se expresa como O(n * m). Si n y m crecen de manera similar, se puede aproximar a O(n²), asumiendo que n ≈ m.

Existe otro bucle que puede tener la misma tipo de asíntota superior:

public static boolean containsDuplicates(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[i] == arr[j]) {
                return true;
            }
        }
    }
    return false;
}Lenguaje del código: PHP (php)

Primer Bucle (Externo):

Este bucle recorre cada elemento del arreglo arr una vez, desde i = 0 hasta i = n – 1.
Por lo tanto, este bucle se ejecuta n veces, donde n es el tamaño del arreglo.

Segundo Bucle (Interno):

El segundo bucle depende del valor de i en el primer bucle.
Para cada valor de i, el segundo bucle recorre desde j = i + 1 hasta j = len(arr) - 1.
Esto significa que el segundo bucle no se ejecuta siempre n veces. En su lugar:
- Cuando i=0, j recorre n − 1 elementos.
- Cuando i=1, j recorre n − 2 elementos.
- Cuando i=2, j recorre n – 3 elementos. Y así sucesivamente.

Esto significa que aparecerá la siguiente serie:

(n-1) + (n-2) + (n-3) + ... + 1

Esto es la siguiente serie:

n * (n-1) / 2 = 1/2 * (n² - n)

Esto termina siendo O(n²).

Ejemplo: Ordenación por burbuja

O(n³) – Cúbica

Similar al caso del cuadrático, si colocamos 3 ciclos anidados siempre será una potencia. En este caso de grado 3. Esto significa que si tenemos k anidamientos es probable que tengamos un O(n^k).

for(i=0; i<n; i++){              // O(n)
   for(j=0; j<m; j++){           // O(n*m)
       for(k=0; k<p; k++){       // O(n*m*p)
          ...
       }
   }
}Lenguaje del código: JavaScript (javascript)

Este es similar: Si n, m y p se pueden unificar. Lo cual genera una potencia de 3. Con lo cual queda un O(n³)

O(2^n) – Exponencial

La complejidad crece exponencialmente, volviéndose rápidamente ineficiente.

Ejemplo: Calcular el término n de la serie de Fibonacci de forma recursiva.

public int fibonacci(int n) {
    if (n <= 1) {
        return n;
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}Lenguaje del código: PHP (php)

O(n!) – Factorial

La complejidad factorial aparece en algoritmos que requieren evaluar todas las permutaciones posibles.

Ejemplo: Generar todas las permutaciones de una lista.

public List<List<Integer>> permutaciones(List<Integer> lista) {
    List<List<Integer>> resultado = new ArrayList<>();
    if (lista.isEmpty()) {
        resultado.add(new ArrayList<>());
        return resultado;
    }
    Integer primerElemento = lista.remove(0);
    List<List<Integer>> subPermutaciones = permutaciones(lista);
    for (List<Integer> subLista : subPermutaciones) {
        for (int i = 0; i <= subLista.size(); i++) {
            List<Integer> nuevaPermutacion = new ArrayList<>(subLista);
            nuevaPermutacion.add(i, primerElemento);
            resultado.add(nuevaPermutacion);
        }
    }
    lista.add(0, primerElemento); // Restaurar la lista original
    return resultado;
}Lenguaje del código: PHP (php)

Relacionado

Etiquetado big-O, bucles