algorismo

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
Tipos de 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 en funció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 fi ¥
Notación O O(g(n)) = { f(n) | $c,n0 constantespositivas tales que f (n) = c g(n) " n = n0 }
En la práctica, se ignoran las constantes y los términos de menor peso: 33n + 90n23 – 5n + 6046 = O(n)
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 eficienteque
un algoritmo O(n
es más eficiente que
un algoritmo O(n2)
3)
es más eficiente que
un 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 unalgoritmo
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 del nú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...