Tarea 2 - Analisis de Algoritmos

ANÁLISIS DE ALGORITMOS

CB-102

TAREA # 2

Fecha de entrega: enero 30

1. Ordena las siguientes funciones por orden de crecimiento; es decir, encuentra un arreglo g1, g2, …,g20 de las funciones que satisfaga g1 = O(g2), g2 = O(g3),…, g19 = O(g20). Parte la lista en clases equivalentes de forma que g(n) y f(n) estén en la misma clase si y sólo si g(n) =(f(n)).

Ordenados quedan:

[pic 2]

1. a)        Escribe un algoritmo para encontrar la mediana de tres enteros distintos a, b y c.

[pic 3]

1. Describe D, el conjunto de entradas para tu algoritmo, a la luz de la discusión del ejemplo de búsqueda secuencial en la cual se calculó el tiempo promedio.

1. ¿Cuántas comparaciones efectúa tu algoritmo en el peor de los casos? ¿En el promedio?

En el peor caso: 3 comparaciones

En promedio: 1/6 (2+3+3+2+3+3)=16/6=8/3

1. ¿Cuántas comparaciones son necesarias en el peor de los casos para encontrar la mediana de tres números?

Número de comparaciones en el peor de los casos: 3 comparaciones

1. Supón que la función Q está definida para todas las potencias de 2, y está descrita mediante la siguiente relación de recurrencia y condición frontera :

Q(n) = n – 1 + 2 Q(n/2) ; Q(1) = 0

Encuentra una forma cerrada para Q.

Hint : haz el siguiente cambio de variable. n = 2k. Con este cambio, escribe Q(n) = Q(2k) = T(k) y escribe la recurrencia en función de k.

...