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

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

En el algoritmo 1.2, al contar la cantidad de veces que se ejecuta cada línea, se ve que las líneas 1
y 7 lo hacen una vez cada una. La línea 2 se ejecuta n+1 veces, en la línea 3 se encuentra un ciclo
anidado dentro del ciclo controlado por la variable i; entonces, por cada iteración del primer ciclo, la
línea 3 se repite n+1 veces. Pero por cada vez que se repita el ciclo de la línea 2, la línea 4 se ejecuta
n veces. Por lo tanto, la complejidad es f(n)=1+n+1+n(n+1)+n(n)+1; luego, reduciendo términos, se
obtiene f(n)=2n^2+2n+3. En consecuencia, se dice que la complejidad es de un polinomio de se-
gundo grado.

Diferentes algoritmos pueden tener complejidades iguales o similares, como se enseña a continua-
ción en el algoritmo 1.3.

Algoritmo 1.3. Ejemplo de dos ciclos anidados con diferentes números de repeticiones cada uno

Del mismo modo que en el algoritmo, las líneas 1 y 7 se ejecutan una vez. La línea 2 se ejecuta n+1
veces. Para el ciclo controlado por j, sus repeticiones están en función del valor de i. De esta mane-
ra, cuando i=1, entonces la línea 4 se ejecuta una vez; cuando i=2, entonces la línea 4 se ejecuta 2
veces, pero hay que sumarle la cantidad de veces que se ejecutó cuando i=1; por lo tanto, el total
es 1+2=3. Cuando i=3, entonces la línea 4 se ejecuta 3 veces, pero sumando la cantidad de veces
que se ejecutó cuando i=1 y i=2, el total es 1+2+3=6.
Por inducción se establece que la línea 4 se repite , pero como i=n, entonces .

Así, la suma se establece como reduciendo términos,
se obtiene

Por lo tanto, la complejidad de este algoritmo es un polinomio de segundo grado. Véase que los poli-
nomios del y del tienen el mismo grado, aunque sean diferentes los polinomios. Esto significa que los
dos tienen la misma complejidad, mientras que en el Algoritmo 1.1 la complejidad es menor porque
su polinomio es de inferior orden (es decir, realiza menos pasos u operaciones).

11