Algoritmos

Análisis de algoritmos
• Eficiencia de un algoritmo • Técnicas de diseño de algoritmos

Bibliografía
Robert Sedgewick: “Algorithms in C” Addison-Wesley, 1990 ISBN 0201514257 Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: “Data Structures and Algorithms” Addison-Wesley, 1983 ISBN: 0201000237 Mark Allen Weiss “Data Structures and Algorithm Analysis in C” Addison-Wesley, Second Edition,1996 ISBN 0201498405 Thomas H. Cormen, Charles E. Leiserson & Ronald L. Rivest “Introduction to Algorithms” MIT Press, 1990 ISBN 0262031418 Giles Brassard & Paul Bratley “Fundamentals of Algorithmics” Prentice Hall, 1996 ISBN 0133350681 “Fundamentos de Algoritmia” Prentice Hall, 1997 ISBN 848966000X

Eficiencia de un algoritmo
El análisis de algoritmos estudia, desde el punto de vista teórico,los recursos computacionales que necesita la ejecución de un programa de ordenador: su eficiencia. p.ej. Tiempo de CPU Uso de memoria Ancho de banda … NOTA: En el desarrollo real de software, existen otros factores que, a menudo, son más importantes que la eficiencia: funcionalidad, corrección, robustez, usabilidad, modularidad, mantenibilidad, fiabilidad, simplicidad… y el tiempo del programador.¿Por qué estudiar la eficiencia de los algoritmos? Porque nos sirve para establecer la frontera entre lo factible y lo imposible. Ejemplo: Algoritmos de ordenación Observación El tiempo de ejecución depende del tamaño del conjunto de datos. Objetivo Parametrizar el tiempo de ejecución en función del tamaño del conjunto de datos, intentando buscar una cota superior que nos sirva de garantía Tiposde análisis Peor caso (usualmente) T(n) = Tiempo máximo necesario para un problema de tamaño n Caso medio (a veces) T(n) = Tiempo esperado para un problema cualquiera de tamaño n • Requiere establecer una distribución estadística Mejor caso (engañoso)

Análisis de Algoritmos

1

© Fernando Berzal

Análisis del peor caso ¿Cuál es el tiempo que necesitaría un algoritmo concreto? û Varía enfunción del ordenador que utilicemos. û Varía en función del compilador que seleccionemos. û Puede variar en función de nuestra habilidad como programadores. IDEA: Ignorar las constantes dependientes del contexto SOLUCIÓN: Fijarse en el crecimiento de T(n) cuando n → ∞

Notación O O(g(n)) = { f(n) | ∃c,n0 constantes positivas tales que f (n) = c g(n) ∀ n = n0 }

En la práctica, se ignoran lasconstantes y los términos de menor peso: 3n3 + 90n2 – 5n + 6046 = O(n3) Eficiencia asintótica Cuando n es lo suficientemente grande… un algoritmo O(1)
es más eficiente que

un algoritmo O(log n)
es más eficiente que

un algoritmo O(n)
es más eficiente que

un algoritmo O(n log n)
es más eficiente que

un algoritmo O(n2)
es más eficiente que

un algoritmo O(n3)
es más eficiente queun algoritmo O(2n)

NOTA:

En ocasiones, un algoritmo más ineficiente puede resultar más adecuado para resolver un problema real ya que, en la práctica, hay que tener en cuenta otros aspectos además de la eficiencia.

Análisis de Algoritmos

2

© Fernando Berzal

Análisis de la complejidad de un algoritmo
Propiedades de la notación O c O(f(n)) = O(f(n)) O(f(n)+g(n)) = max{O(f(n)), O(g(n)) } O(f(n)+g(n)) = O(f(n)+g(n)) O(f(n))O(g(n)) = O(f(n)g(n)) O(O(f(n))) = O(f(n)) Asignaciones y expresiones simples x = x+1; T(n) = O(1)

Secuencias de instrucciones I1; I2;

T(n) = T1(n) + T2(n) = max { O(T1(n)), O(T2(n)) }

Estructuras de control condicionales (if-then-else) T(n) = O (Tcondición(n)) + max { O(Tthen(n)), O(Telse(n)) } Estructuras de control iterativas Producto delnúmero de iteraciones por la complejidad de cada iteración. Si la complejidad varía en función de la iteración, obtenemos una sumatoria. Si no conocemos con exactitud el número de iteraciones (bucles while y do-while), se estima este número para el peor caso. Algoritmos recursivos Se obtienen recurrencias que hay que resolver…

Análisis de Algoritmos

3

© Fernando Berzal

Ejemplo:...