Algoritmos

Análisis de Algoritmos

Deber N° 1

1.- Escriba el seudo código para el algoritmo que ordena una secuencia por selección. Discuta por que es correcto este algoritmo. Exprese en notación teta()los tiempos de ejecución para el peor y para el mejor de los casos de este algoritmo.

2.- Considere el algoritmo de búsqueda secuencial (o lineal) cuando la secuencia no necesariamente esta ordenada.En promedio, ¿cuantos elementos de la secuencia necesitan ser comparados?, suponga que el elemento buscado podría ser cualquiera con la misma probabilidad. ¿Cuantas comparaciones son necesarias enel peor de los casos? Exprese los tiempos de ejecución promedio y en el peor de los casos de este algoritmo empleando la notación-teta.

3.- Con respecto al problema de buscar al elemento x en unasecuencia A de longitud n, note que si la secuencia esta ordenada y comparamos x con el elemento en la mitad de la secuencia, la búsqueda de x en la secuencia se reduce a la búsqueda de x en unasecuencia ordenada de tamaño aproximadamente igual a la mitad del tamaño de A. El algoritmo de búsqueda binaria repite este procedimiento, dividiendo cada vez la porción restante de la secuencia por 2.Discuta lo correcto de esta solución. Escriba el seudo código de este procedimiento de búsqueda, ya sea en la forma recursiva o iterativa. Argumente a favor de la hipótesis de que el tiempo de ejecución deeste algoritmo en el peor de los casos es teta(lg n). (lg n es el logaritmo base 2 de n)

4.- Diga si la hipótesis 2n+1 = O(2n) es verdadera. Diga si 22n = O(2n) lo es.

5.- Demuestre que eltiempo de ejecución del un algoritmo es Θ(g(n)) si y solo si el tiempo de ejecución del peor de los casos es O(g(n)) y del mejor de los casos es Ω(g(n)).

6.- Sea A[1..n] una secuencia de n númerosdistintos. Se define como inversión de A al par (i, j) tal que siendo i A[j].

• Liste las cinco inversiones de la secuencia 2, 3, 8, 6, 1
• Que secuencia de elementos tomados del conjunto 1,...