Ep 01
Ep 01
Ep 01
Pregunta 1:
Considere ordenar n números almacenados en el array A, en el siguiente modo:
encontrando primero el elemento más pequeño de A e intercambiarlo con el elemento de A [1]. Luego encuentra
el segundo elemento más pequeño de A e intercambiarlo con A [2]. Continúe de esta manera por los primeros
n-1 elementos de A.
1.1 Escriba el pseudocódigo para este algoritmo, que se conoce como Selección
Sort:
1.2 Dar el tiempo de ejecución en el peor y mejor de los casos usando la notación
Teta:
Si analizamos el algoritmos podemos determinar que este siempre analizará toda la lista para cualquier caso
por lo que tanto el peor como el mejor caso tendrán la misma complejidad.
Ahora sumamos los valores de las repeticiones por el costo de cada linea
Pn−1 Pn−1 Pn−1
T (n) = c1 ∗ (n − 1) + c2 ∗ (n − 1) + c3 ∗ t=1 t + c4 ∗ t=1 t + c5 ∗ t=1 t
+c6 ∗ (n − 1) + c7 (n − 1)c8 ∗ (n − 1)
Pn
T (n) = (c3 + c4 + c5 ) ∗ t=1 t + (c1 + c2 + c6 + c7 + c8 ) ∗ (n − 1)
T (n) = (c3 + c4 + c5 ) ∗ n(n−1)
2 + (c1 + c2 + c6 + c7 + c8 ) ∗ n − (c1 + c2 + c6 + c7 + c8 )
2
T (n) = (c3 + c4 + c5 ) ∗ n 2−n + (c1 + c2 + c6 + c7 + c8 ) ∗ n − (c1 + c2 + c6 + c7 + c8 )
c3 +c4 +c5
T (n) = 2 ∗ (n2 − n) + (c1 + c2 + c6 + c7 + c8 ) ∗ n − (c1 + c2 + c6 + c7 + c8 )
c3 +c4 +c5
∗ n2 − c3 +c24 +c5 ∗ n + (c1 + c2 + c6 + c7 + c8 ) ∗ n − (c1 + c2 + c6 + c7 + c8 )
T (n) = 2
c3 +c4 +c5
∗ n2 + c1 + c2 + c6 + c7 + c8 − c3 +c24 +c5 ∗ n − (c1 + c2 + c6 + c7 + c8 )
T (n) = 2
Finalmente en notación Θ el algoritmo tendrá un tiempo de ejecución de T (n) = Θ(n2 ) tanto en el mejor como
en el peor caso.
Pregunta 2:
Resuelva la recurrencia T (n) = 3T (n/2) + n2 − n. Si T (1) = 1, para todo n ≥ 2 potencias de 2. Muestre todas
sus operaciones:
Pregunta 3:
Calcular el tiempo de ejecución del algoritmo Quicksort cuando se emplea el procedimiento RANDOMIZED-
PARTITION
Pregunta 4:
Indicar el tiempo de ejecución en el mejor, medio, y peor de los casos para los algoritmos: Quick Sort, Heap
Sort, Counting Sort, Radix Sort y Bucket Sort: