Solucionario Taller I
Análisis y Diseño de Algoritmos I
Profesor: Jesus Alexander Aranda Bueno
Monitor: Samuel Galindo Cuevas
2024-II
Punto 1 [0.5pts]
En cada literal se encontrará un algoritmo escrito en pseudo-código. Para cada algoritmo,
debe expresar su orden de complejidad, indicando las sumatorias que reflejen el T(n) (no
requiere explicación adicional. Hágalo en términos de Θ). La operación básica en los
siguientes algoritmos son las lı́neas print(“Hola Mundo”):
a.
proc1(n)
for(i = 1; i <= n; i= i * 2)
for(j = 1; j <= n; j = j + 2)
print("Hola Mundo")
De la sumatoria interna dado que se va sumando de 2 en 2 tenemos una sumatoria de la
forma:
n/2
X
1
j=1
De la sumatoria externa teniendo en cuenta que se multiplica por 2, esto se podria ver
como un logaritmo en base 2, por tanto obtenemos:
log(n) n/2
X X
1
i=1 j=1
1
Resolviendo la expresión, se tiene:
log(n) n/2 log(n)
X X X n n
1= = log(n) ∗
i=1 j=1 i=1
2 2
La complejidad es entonces Θ(nlog(n)).
b.
proc2(n)
for(i = 1; i <= n; i= i + 2)
for(j = 1; j <= n * n; j = j * 2)
print("Hola Mundo")
De la sumatoria interna dado que el limite es n2 y la forma en que crece el indice es
logaritmica se obtiene:
n/2
X
1
j=1
De la sumatoria externa teniendo en cuenta que suma de 2 en 2 obtenemos:
2
n/2 log(n )
X X
1
i=1 j=1
Resolviendo la expresión, se tiene:
2
n/2 log(n ) n/2
X X X n
1= log(n2 ) = ∗ 2log(n) = n ∗ log(n)
i=1 j=1 i=1
2
La complejidad es entonces Θ(nlog(n)).
c.
proc3(n)
for(i = 1; i <= 2000000; i= i +1)
for(j = 1; j <= 3000000; j = j + 1)
for(k = 1; k <= 1600000; k = k+1)
print("Hola Mundo")
Para empezar, la tercera sumatoria tiene una parada constante en 1600000, además de
un incremento de 1, con lo anterior se obtiene:
1600000
X
1
k=1
2
La segunda sumatoria tiene una parada constante en 3000000, además de un incremento
de 1, con lo anterior se obtiene:
3000000
X 1600000
X
1
j=1 k=1
La sumatoria externa tiene una parada constante en 2000000, además de un incremento
de 1, con lo anterior se obtiene:
2000000
X 3000000
X 1600000
X
1
i=1 j=1 k=1
Resolviendo la expresión, se tiene:
2000000
X 3000000
X 1600000
X
1 = 2000000 ∗ 3000000 ∗ 1600000
i=1 j=1 k=1
Teniendo en cuenta que todas las sumatorias son constantes. La complejidad es entonces
Θ(1).
d.
proc4(n)
for(i = 1; i <= n; i= i * 2)
for(j = 1; j <= n; j = j * 4)
print("Hola Mundo")
De la sumatoria interna dado que el limite es n y la forma en que crece el indice es
logaritmica con base 4 se obtiene:
log4 (n)
X
1
j=1
De la sumatoria externa teniendo en cuenta que su incremento es logaritmico en base 2:
log(n) log4 (n)
X X
1
i=1 j=1
Resolviendo la expresión, se tiene:
log(n) log4 (n) log(n)
X X X
1= log4 (n) = log(n) ∗ log4 (n)
i=1 j=1 i=1
La complejidad es entonces Θ(log 2 (n)).
3
e.
proc5(n)
for(i = 1; i <= n * n; i= i + i)
for(j = 1; j <= n * n * n; j = j * 4)
print("Hola Mundo")
De la sumatoria interna dado que el limite es n3 y la forma en que crece el indice es
logaritmica con base 4 se obtiene:
3log4 (n)
X
1
j=1
De la sumatoria externa teniendo en cuenta que su incremento es logaritmico en base 2
y su limite es n2 :
2log(n) 3log4 (n)
X X
1
i=1 j=1
Resolviendo la expresión, se tiene:
2log(n) 3log4 (n) 2log(n)
X X X
1= 3log4 (n) = 2log(n) ∗ 3log4 (n)
i=1 j=1 i=1
La complejidad es entonces Θ(log 2 (n)).
Punto 2 [1.0 pts]
Dado el siguiente algoritmo:
1 Misterio ( a [1.. n ]) linea 1
2 {
3 n = a . length ; linea 2
4 aux1 = a [1]; linea 3
5 aux2 = a [1]; linea 4
6 k = 2; linea 5
7 while ( k <= n ) linea 6
8 {
9 if ( a [ k ] < ( aux1 + a [ k ]) ) linea 7
10 aux1 = a [ k ]; linea 8
11 else linea 9
12 aux1 = aux1 + a [ k ]; linea 10
13
14 aux2 = aux1 ; linea 11
15
16 k ++; linea 12
17 }
18 return aux2 ; linea 13
19 }
4
Asuma que la entrada del anterior programa es un arreglo de n enteros. Ponga su
atención en 2 casos, primero una lista de enteros mayores a 0 ordenada descendentemente
y el segundo caso una lista de enteros menores a 0 ordenada ascendentemente.
a. De una explicación breve del algoritmo para cada caso expuesto anteriormente y ex-
plique que retorna cada caso.
Caso lista de enteros mayores a 0 ordenada descendentemente:
El algoritmo siempre entrará en el bloque if, ya que la suma de aux1 + a[k] siempre será
mayor que a[k], dado que tanto aux1 como a[k] son números positivos. En cada iteración,
se ejecutará la operación de la lı́nea 8, que actualiza aux1 con el valor de a[k] de modo
que aux1 tomará el valor menor. A continuación, se asignará el valor actualizado de aux1
a aux2, y luego se incrementará el ı́ndice k. Al finalizar el ciclo, el valor de aux2 será el
menor elemento del arreglo.
Caso lista de enteros menores a 0 ordenada ascendentemente:
El algoritmo entrará en el bloque else, ya que la suma de aux1 + a[k] siempre será menor
que a[k], dado que tanto aux1 como a[k] son números negativos. En este caso, la op-
eración de la lı́nea 10 asignara a aux1 el valor de aux1 + a[k], de modo que aux1 tomará
la suma de aux1 + [k]. Posteriormente, aux1 se copiará en aux2 y el ı́ndice k se incremen-
tará. Al final del ciclo, aux2 contendrá el valor de la suma de todos los numeros negativos.
b. ¿Cuál es el numero maximo y minimo de veces que se podrı́a ejecutar la asignación
de la linea 8 y la linea 10? Justifique su respuesta y muestre un ejemplo donde ocurra esto.
Minimo numero de repeticiones linea 8 y maximo numero de repeticiones
linea 10:
Cuando todos los numeros son positivos sin importar el orden la linea 8 se ejecutará n-1
veces mientras que la linea 10 se ejecutara 0 veces. Un ejemplo de esto:
[5, 10, 2]; k=2; a[k] = 10; aux1 = 5
10 < 5 + 10 (caso if); k = 3; a[k] = 2; aux1 = 10
2 < 10 + 2 (caso if); k = 4; aux1 = 2
if = n-1 (3-1 repeticiones); else = 0 repeticiones.
Minimo numero de repeticiones linea 10 y maximo numero de repeticiones
linea 8:
CCuando todos los numeros son positivos sin importar el orden la linea 10 se ejecutará 0
veces mientras que la linea 8 se ejecutara n-1 veces. Un ejemplo de esto:
[-5, -10, -2]; k=2; a[k] = -10; aux1 = -5
-10 -5 + (-10) (caso else); k = 3; a[k] = 2; aux1 = -15
-2 < -15 + (-2) (caso else); k = 4; aux1 = -17
if = 0 repeticiones; else =n-1 (3-1 repeticiones);
5
d. Determine la complejidad del algoritmo de la manera mas precisa posible, con-
sidere el mejor y peor caso, hágalo en terminos de Θ(), O() u Ω() o dos o todos ellos
segun lo que considere conveniente.
La complejidad del algoritmo teniendo en cuenta el bucle while que va desde 2 hasta n, se
observa claramente que se ejecuta un total de n-1 veces, por lo cual tiene una complejidad
de Θ(n)
Punto 3 [1.0 pts]
Dado el siguiente algoritmo:
1 Program misterio2 ( a [1 ... n ]) { /* linea 1 */
2 n = a . length ; /* linea 2 */
3 aux1 = 0; /* linea 3 */
4
5 for ( k = 1; k <= n ; k = k + 1) { /* linea 4 */
6 if ( fAux ( a [ k ]) ) { /* linea 5 */
7 aux1 = aux1 + 1; /* linea 6 */
8 } else { /* linea 7 */
9 aux1 = aux1 - 1; /* linea 8 */
10 }
11 }
12
13 return aux1 / n ; /* linea 9 */
14 }
15
16 function fAux ( x ) { /* linea 10 */
17 if ( x <= 1) return false ; /* linea 11 */
18 for ( i = 2; i * i <= x ; i = i + 1) { /* linea 12 */
19 if ( x % i == 0) return false ; /* linea 13 */
20 }
21 return true ; /* linea 14 */
22 }
a. ¿Que hace el algoritmo fAux? ¿Cual es su complejidad temporal?.
El algoritmo fAux determina si un numero es primo o no, si el valor x es menor o igual
a 1, retorna falso debido a que ningun numero por debajo de 1 es primo. si x > 1, el
algoritmo itera desde i = 2 hasta i2 <= x verificando si x es divisible por i mendiante la
operación modulo, retornando true si ningun i divide a x.
El mejor de los casos es cuando x toma un valor <= 1 obteniendo una complejidad de Ω(1).
Para el peor de los casos, su complejidad temporal vendria dada por la cantidad de
2
veces que itera el bucle for, que en este caso seria
√ i <= x con un incremento de i + 1
por tanto
√ para simplificar esto, tendriamos i <= x, por tanto el √
numero de iteraciones
serian ⌊ x⌋ − 1 ya que empieza en i = 2. Su complejidad serı́a O( x).
6
b. ¿El valor que retorna el programa a que corresponde según el arreglo de entrada?
¿cual es el mayor y el valor menor que este puede tomar? de ejemplo de esto, Justifique
claramente su respuesta.
Para empezar se tiene el contador aux1, además se tiene el for que itera n veces, este
bucle contiene un condicional, el cual suma 1 si el valor a[k], es primo, de lo contrario
resta 1 al contador, la linea 9 retorna aux1
n , lo cual siempre tendrá un valor entre [−1, 1],
si por debajo de 0 quiere decir que la cantidad de numeros no primos es mayor que la de
primos, si es igual a 0 significa que hay igual cantidad de primos que de no primos, por
ultimo si es mayor a 0 quiere decir que la cantidad de numeros primos en el arreglo es
mayor que la de no primos.
El mayor valor que puede tomar es 1, un ejemplo seria:
[2,3,5,7,11], teniendo en cuenta que todos son primos y el tamaño del arreglo es 5, ten-
driamos:
5
5 =1
El menor valor que puede tomar es -1, un ejemplo seria:
[-2,-3,-5,-7,-11], teniendo en cuenta ninguno de los numeros del arreglo es primo y el
tamaño del arreglo es 5, tendriamos:
−5
5 = −1
c. Determine la complejidad del algoritmo teniendo en cuenta la función auxiliar de
la manera mas precisa posible, considere el mejor y peor caso, hágalo en terminos de Θ(),
O() u Ω() o dos o todos ellos segun lo que considere conveniente.
Para hallar la complejidad tomaremos el condicional de la linea 5 como linea basica,
esta linea se realiza un total de n veces, ahora tomaremos el peor y el mejor caso de la
función fAux.
Para el mejor caso tendremos un arreglo con valores iguales o inferiores a uno, por
tanto tendriamos una complejidad de Θ(n) ∗ Ω(1) = Ω(n).
Para el peor caso tendremos un arreglo
√ con valores
√ superiores a 1 en el arreglo, obte-
niendo una complejidad de Θ(n) ∗ O( x) = O(n ∗ x).
7
Punto 4 [1.0 pts]
1. Sort(a[1..n])
2. for i = 1 to n − 1
3. min = i
4. for j = i + 1 to n
5. if A[j] < A[min]
6. min = j
7. intercambiar(A[min], A[i])
a. Identifique una lı́nea básica adecuada y determine su complejidad. Determine si existe
un peor y mejor caso.
La linea basica tomada será la comparación de la linea 5, la complejidad del algoritmo se
basará en los bucles for, para empezar el bucle externo itera n − 1 veces, debido a que j
es = i + 1, el bucle interno entrará una vez menos por cada itreación del bucle externo,
por tanto obtenemos:
n(n−1)
(n − 1) + (n − 2) + ... + 1 = 2
y teniendo en cuenta que el algoritmo siempre realizará las mismas iteraciones no
existe un mejor ni un peor caso. La complejidad es: Θ(n2 )
b. Determine si este algoritmo es estable asumiendo que puede haber elementos repeti-
dos en el arreglo de entrada.
Un algoritmo es estable siempre que luego de ordenar sus elementos, el orden relativo que
tenı́an los elementos de igual valor se mantiene. El algoritmo no es estable, para demostrar
esto basta con presentar un ejemplo donde el orden relativo se pierde. Considere la entrada
a = [5∗ , 5∗∗ , 1], al aplicar el algoritmo en cada iteración del for exterior se tiene:
sort([5∗ , 5∗∗ , 1])
→ [1, 5∗∗ , 5∗ ]
→ [1, 5∗∗ , 5∗ ]
Note que 5∗ al momento de ejecutar el algoritmo se encontraba antes de 5∗∗ , sin embargo
al terminar el orden relativo se ha perdido y 5∗ se encuentra después de 5∗∗ , por lo tanto
se ha demostrado que el algoritmo no es estable. Para lograr que el algoritmo sea estable,
basta con cambiar la lı́nea 5 por if a[j] <= a[min].
Punto 5 [0.5 pts]
En cada literal se encontrará un algoritmo escrito en pseudo-código. Para cada algoritmo,
debe expresar su orden de complejidad, indicando las ecuaciones de recurrencias que
8
reflejen el T(n) (no requiere explicación adicional. Hágalo en términos de Θ). La operación
básica en los siguientes algoritmos son las lı́neas print(“Hola Mundo”):
a.
funcion1(n)
if(n<=1)
print("Hola Mundo")
else
print("Hola Mundo")
print("Hola Mundo")
Funcion1(n/2)
Funcion1(n/2)
La parte no recursiva tiene costo constante, se realizan dos llamados recursivos, entonces,
la expresión es entonces T (n) = 2T n2 +1, a la cual es posible aplicar el método maestro,
donde a = 2 y b = 2, y la parte no recurrente tiene una complejidad constante, es decir,
θ(1). Entonces:
nlog2 (2) vs θ(1)
n1 vs θ(1)
La parte recurrente es aquella que tiene mayor crecimiento, por lo tanto la complejidad
está dada por tal parte del algoritmo, es decir, la complejidad es θ(n).
b.
funcion2(n)
if(n<=1)
print("Hola Mundo")
else
for(i = 1; i <=5; i= i+1)
funcion2(n/4)
funcion2(n/4)
El bucle for se ejecuta 5 veces ya que tiene parada constanste, además se ejecutan 2
llamados recursivos, por tanto, la expresión es entonces T (n) = 10T n4 + 1, a la cual es
posible aplicar el método maestro, donde a = 10 y b = 4, y la parte no recurrente tiene
una complejidad constante, es decir, θ(1). Entonces:
nlog4 (10) vs θ(1)
n1.66 vs θ(1)
La parte recurrente es aquella que tiene mayor crecimiento, por lo tanto la complejidad
está dada por tal parte del algoritmo, es decir, la complejidad es θ(n1.66 ).
c.
9
funcion3(n)
if(n<=1)
print("Hola Mundo")
else
for(i = 1; i <= n; i = i+1)
for(j = 1; j<=n; j = j * 2)
print("Hola Mundo")
funcion3(n/3)
funcion3(n/3)
funcion3(n/3)
Debido a que la parte no recursiva ejecuta 2 bucles, que tendrian complejidad
Θ(n∗log(n)),
se realizan tres llamados recursivos, teniendo una ecuación T (n) = 3T n3 + n ∗ log(n), a
la cual es posible aplicar el método maestro, donde a = 3 y b = 3, y la parte no recurrente
tiene una complejidad n ∗ log(n). Entonces:
nlog3 (3) vs n ∗ log(n).
n1 vs n ∗ log(n)
La parte no recurrente es aquella que tiene mayor crecimiento, por lo tanto la complejidad
está dada por tal parte del algoritmo, es decir, la complejidad es θ(n ∗ log(n)).
d.
funcion4(n)
if(n==1)
print("Hola Mundo")
else
for(i = 1; i<=n * n; i= i+1)
print("hola mundo")
funcion4(n/2)
funcion4(n/2)
funcion4(n/2)
funcion4(n/2)
Debido a que la parte no recursiva ejecuta un bucle, que tendrian complejidad Θ(n2 ), se
realizan cuatro llamados recursivos, teniendo una ecuación T (n) = 4T n2 + n2 , a la cual
es posible aplicar el método maestro, donde a = 4 y b = 2, y la parte no recurrente tiene
una complejidad n2 . Entonces:
nlog4 (2) vs n2 .
n2 vs n2
Esto es un empate, por lo cual, caeria en el caso 2 tel teorema maestro, obteniendo una
complejidad de Θ(n2 ∗ log(n))
10
Punto 6 [1.0 pts]
Analice los sigiuientes arreglos:
A= 49 12 23 45 67 34 10 78 56 11 3 88
B= 2 8 29 44 52 89 100 128 256 388 400 401
C= 5 3 8 3 9 1 5 2 5 3 7 8
Aplicando los algoritmos MergeSort, QuickSort, InsertionSort:
a. Para cada arreglo determine la complejidad que tendria ordenarlos con los algoritmos
mencionados anteriormente.
Arreglo A:
Mergesort: O(nlog(n))
QickSort: O(nlog(n))
InsertionSort: O(n2 )
Arreglo B:
Mergesort: Θ(nlog(n))
QickSort: Θ(n2 )
InsertionSort: O(n)
Arreglo C:
Mergesort: Θ(nlog(n))
QickSort: Θ(nlog(n))
InsertionSort: Θ(n2 )
b. Mencione cual algoritmo es mejor para cada arreglo, en caso de que dos algoritmos
tengan la misma complejidad temporal, elija uno y de argumentos del porque es mejor el
algoritmo escogido. (puede usar argumentos como complejidad espacial y estabilidad)
Arreglo A:
Para este caso el mejor algoritmo seria MergeSort ya que, es un algoritmo establee y no
depende tanto del pivote, como lo seria QuickSort.
Arreglo B:
Para este caso el mejor algoritmo seria InsertionSort ya que se presenta el mejor caso
(arreglo ya ordenado).
Arreglo C:
Teniendo como base que MergeSort y QuickSort se comportan bastante similar y el arreglo
tiene valores repetidos, el mejor algoritmo seria MergeSort ya que garantiza la estabilidad.
11
