Page 27 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
P. 27
INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
c = N;
while (c > 1) {
algo_de_ O (1);
c/= 2;
}
Un razonamiento análogo nos lleva a log(N) iteraciones y, por tanto, a un orden O (log n) de comple-
jidad.
for (int i = 0; i < N; i++) {
c = i;
while (c > 0) {
algo_de_ O (1);
c/= 2;
}
}
Tenemos un bucle interno de orden O (log n) que se ejecuta N veces, luego el conjunto es de orden
2
O (n log n).
• Llamadas a procedimiento
La complejidad de llamar a un procedimiento viene dada por la complejidad del
contenido del procedimiento en sí. El coste de llamar no es sino una constante que
se puede obviar inmediatamente dentro de los análisis asintóticos.
El cálculo de la complejidad asociada a un procedimiento puede complicarse no-
tablemente si se trata de procedimientos recursivos.
• Relaciones de recurrencia
En el cálculo de la complejidad de un algoritmo a menudo aparecen expresiones
recursivas para estimar el tiempo que se tarda en procesar un problema de un
cierto tamaño N.
Por ejemplo, se puede hallar un programa que para resolver un problema de ta-
maño N resuelve dos problemas de tamaño N/2 y luego combina las soluciones
parciales con una operación de complejidad O (n).
21
