Análisis De Algoritmos.

Unidad 1. Análisis de algoritmos.

El Análisis de algoritmos es una parte importante de una Teoría de complejidad computacional más amplia, que provee estimaciones teóricas para los recursos que necesita cualquier algoritmo que resuelva un problema computacional dado. Estas estimaciones resultan ser bastante útiles en la búsqueda de algoritmos eficientes.

1.1 Concepto de Complejidad de algoritmos.

Un algoritmo es una secuencia de instrucciones que determina completamente en el comportamiento.

La complejidad de un algoritmo es el ‘orden de crecimiento’ de la función C(n), donde c(n) representa el número de ‘operaciones elementales’ requeridas, en el peor de los casos, en función del tamaño n de la entrada.

(Medida independiente de la arquitectura del computador).

Objetivo del algoritmo Operaciones elementales

Ordenación de una lista de números Comparaciones, intercambios

Resolución de un sistema de ecuaciones lineales Productos, sumas

Pero las consideraciones de eficiencia fundamentales son: el tiempo y el espacio. La complejidad del espacio de un programa es la cantidad de memoria que se necesita para ejecutar hasta la compleción (terminación).La complejidad del tiempo de un programa es la cantidad de tiempo de computadora que se necesita para ejecutar hasta la compleción al considerar estos dos aspectos podremos tener la medida exacta de tiempo y espacio del cual necesitamos para realizar u buen análisis de algoritmos. Un algoritmo será más eficiente comparado con otro, siempre que consuma menos recursos, como el tiempo y espacio de memoria necesarios para ejecutarlo.

1.2 Aritmética de la notación O.

La notación O (también llamada O mayúscula), se utiliza para comparar la eficiencia de los algoritmos.

Tipos de análisis de la Notación O:

*Peor caso (usualmente) T(n) = Tiempo máximo necesario para un problema de tamaño 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 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 ->∞

NOTACION “O”

O(g(n)) = { f(n) | Ec,n0 constantes positivas tales que f (n) = c g(n) A n = n0 }En la práctica, se ignoran las constantes 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),Un algoritmo O

...