Programaion

Estructuras de datos – 2011 – Trabajo Práctico Nº2

1

TRABAJO PRÁCTICO N° 2 ESTRUCTURAS DE DATOS
Departamento de Ciencias e Ingeniería de la Computación - U.N.S. Primer cuatrimestre de 2011Cálculo de tiempo de ejecución
Bibliografía:

[GT] Michael Goodrich & Roberto Tamassia. Data Structures and Algorithms in Java. Fourth Edition. John Wiley and Sons. 2006. [W] Mark A. Weiss.Estructuras de datos. Addison-Wesley Iberoamericana España, S.A. 2000.
Ejercicio 1: Ordene las siguientes funciones por tasa de crecimiento asintótico (asumir que la base de logaritmo es k): 4n log n + 2n210 2 log n 3n + 100 log n 4n 2n n2 + 10n n3 n log n Ejercicio 2: Si el número de operaciones ejecutado por los algoritmos A y B es 8n log n y 2n2 respectivamente. Determine n0 tal que A sea mejor queB para n ≥ n0. Ejercicio 3: Si el número de operaciones ejecutado por los algoritmos A y B es 40n2 y 2n3 respectivamente. Determine n0 tal que A sea mejor que B para n ≥ n0. Ejercicio 4: Muestre quesi d(n) es O(f(n)), entonces ad(n) es O(f(n)) para cualquier constante a > 0. Ejercicio 5: Muestre que 2n+1 es O(2n). Ejercicio 6: Muestre que n2 es Ω(n). Calcule θ(n) para la función n2. Ejercicio 7:Muestre que si d(n) es O(f(n)) y e(n) es O(g(n)), entonces el producto d(n)e(n) es O(f(n)g(n)). Ejercicio 8: Muestre que si d(n) es O(f(n)) y f(n) es O(g(n)), entonces d(n) es O(g(n)). Ejercicio 9:Muestre que si p(n) tiene complejidad polinomial en n, entonces log(p(n)) es O(log(n)). Ejercicio 10: Analice el tiempo de ejecución del algoritmo BinarySum del fragmento de código 3.34.

Estructurasde datos – 2011 – Trabajo Práctico Nº2

2

Ejercicio 11: De una caracterización usando la notación Big-Oh del tiempo de ejecución de los algoritmos Ex1, Ex2, Ex3, Ex4 y Ex5 presentados en elfragmento de código 4.5. Ejercicio 12: Sean P1 y P2 dos programas cuyos tiempos de ejecución son T1(n) y T2(n) respectivamente, donde n es el tamaño de la entrada. Determine para los siguientes casos en...