Page 26 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

Si el tamaño N aparece como límite de iteraciones, surgen varios casos:

caso 1:

for (int i= 0; i < N; i++)

algo_de_ O (1);

N * O (1) = O (n)

caso 2:

for (int i= 0; i < N; i++)

for (int j= 0; j < N; j++)

algo_de_ O (1);

N * N * O (1) = O (n )
2
caso 3:

for (int i= 0; i < N; i++)

for (int j= 0; j < i; j++)

algo_de_ O (1)

El bucle exterior se realiza N veces, mientras que el interior se realiza 1, 2, 3,... N veces, respectiva-
mente. En total, se consigue la suma de una serie aritmética:

1 + 2 + 3 +...+ N = N * (1+N) / 2 > O (n )
2
A veces aparecen bucles multiplicativos, donde la evolución de la variable de control no es lineal
(como en los casos anteriores):

int c = 1;

while (c < N) {

algo_de_ O (1);

c*= 2;

}

El valor inicial de c es 1, siendo 2 al cabo de k iteraciones. El número de iteraciones es tal que 2 N
k
k
=> k = log (N),
2
y, por tanto, la complejidad del bucle es O (log n).

20