Esta sección ofrece varios ejemplos de cómo determinar la O grande para declaraciones de repetición, secuencia y selección.

Ejemplo 1

Considere la complejidad temporal del siguiente bucle:

para (int i = 1; i k = k 5;
}

Es un tiempo constante, c, para ejecutar

k = k 5;

Dado que el bucle se ejecuta n veces, la complejidad temporal del bucle es

T(n) = (una constante c)*n = O(n).

El análisis teórico predice el rendimiento del algoritmo. Para ver cómo funciona este algoritmo, ejecutamos el código del programa siguiente para obtener el tiempo de ejecución para n = 1000000, 10000000, 100000000 y 100000000.

Nuestro análisis predice una complejidad temporal lineal para este bucle. Como se muestra en el resultado de muestra, cuando el tamaño de entrada aumenta 10 veces, el tiempo de ejecución aumenta aproximadamente 10 veces. La ejecución confirma la predicción.

Ejemplo 2

¿Cuál es la complejidad temporal del siguiente bucle?

para (int i = 1; i para (int j = 1; j k = k i j;
}
}

Es un tiempo constante, c, para ejecutar

k = k i j;

El bucle externo se ejecuta n veces. Para cada iteración en el bucle exterior, el bucle interior se ejecuta n veces. Por tanto, la complejidad temporal del bucle es

T(n) = (una constante c)*n*n = O(n^2)

Un algoritmo con complejidad temporal O(n^2) se llama algoritmo cuadrático y exhibe una tasa de crecimiento cuadrática. El algoritmo cuadrático crece rápidamente a medida que aumenta el tamaño del problema. Si duplica el tamaño de entrada, el tiempo del algoritmo se cuadriplica. Los algoritmos con un bucle anidado suelen ser cuadráticos.

Ejemplo 3

Considere el siguiente bucle:

para (int i = 1; i para (int j = 1; j k = k i j;
}
}

El bucle externo se ejecuta n veces. Para i = 1, 2, c, el bucle interno se ejecuta una vez, dos veces y n veces. Por tanto, la complejidad temporal del bucle es

Ejemplo 4

Considere el siguiente bucle:

para (int i = 1; i para (int j = 1; j k = k i j;
}
}

El bucle interno se ejecuta 20 veces y el bucle externo n veces. Por lo tanto, la complejidad temporal del bucle es

T(n) = 20*c*n = O(n)

Ejemplo 5

Considere las siguientes secuencias:

para (int j = 1; j k = k 4;
}

para (int i = 1; i para (int j = 1; j k = k i j;
}
}

El primer bucle se ejecuta 10 veces y el segundo bucle 20 * n veces. Por tanto, la complejidad temporal del bucle es

T(n) = 10*c 20*c*n = O(n)

Ejemplo 6

Considere la siguiente declaración de selección:

if (lista.contiene(e)) {
System.out.println(e);
}
demás
para (Objeto t: lista) {
Sistema.out.println(t);
}

Supongamos que la lista contiene n elementos. El tiempo de ejecución de list.contains(e) es O(n). El bucle en la cláusula else tarda O(n) tiempo. Por lo tanto, la complejidad temporal de toda la declaración es

Ejemplo 7

Considere el cálculo de a^n para un número entero n. Un algoritmo simple multiplicaría n veces, de la siguiente manera:

resultado = 1;
para (int i = 1; i resultado *= a;

El algoritmo tarda O(n) tiempo. Sin pérdida de generalidad, supongamos n = 2^k. Puedes mejorar el algoritmo usando el siguiente esquema:

resultado = a;
para (int i = 1; i resultado = resultado * resultado;

El algoritmo tarda O(logn) tiempo. Para un n arbitrario, puedes revisar el algoritmo y demostrar que la complejidad sigue siendo O(logn).

Por simplicidad, dado que 0(logn) = 0(log2n) = 0(logan), se omite la base constante.