Analisis de algoritmos

ANÁLISIS DE ALGORITMOS

ESTRUCTURA DE DATOS


A LUNES 23 DE AGOSTO DEL 2010
TEMARIO

Introducción
1.1 Concepto de complejidad de algoritmos
1.2 Aritmética de la notación 0
1.3 Complejidad
1.4.1 Tiempo de ejecución de un algoritmo
1.4.2 Complejidad en espacio
1.4 Selección de un algoritmo

INTRODUCCIÓN

S
e define algoritmo como unconjuntofinito de instrucciones no ambiguas y efectivas que indican cómo resolver un problema, producen al menos una salida, reciben cero o más entradas y, para ejecutarse, necesitan una cantidadfinita de recursos.
Cuando existe un problema y para éste también una solución, se puede desarrollar un algoritmo el cual dé paso a la programación de la resolución de dicho problema y las variantes que éstepudiera tener, aunque es verdad que también un problema puede dar paso a varios algoritmos, es necesario hacer elección de uno, la manera de esta selección se puede establecer mediante dos pasos, los cuales son:

a) Criterios orientados a minimizar el costo de desarrollo: claridad, sencillez y facilidad de implantación, depuración y mantenimiento.
b) Criterios orientados a disminuir el costode ejecución: tiempo de procesador y cantidad de memoria utilizados.

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.
Por ejemplo: Tiempo de CPU, uso de memoria, etc.

1.1 CONCEPTO DE COMPLEJIDAD DE LOS ALGORITMOS

La complejidad algorítmica es una métrica teórica que seaplica a los algoritmos en este sentido. Es un concepto que fundamental para todos los programadores, pero sin embargo, a menudo se desconoce por completo.
La complejidad de un algoritmo se puede deducir mediante técnicas matemáticas que nos conduce a la reducción de selección de los algoritmos obtenidos para un problema.

La forma matemática anteriormente mencionada es la siguiente:
Lafunción complejidad, f(n); donde n es el tamaño del problema, da una medida de la cantidad de recursos que un algoritmo necesitará al implantarse y ejecutarse en alguna computadora. Puesto que la cantidad de recursos que consume un algoritmo crece conforme el tamaño del problema se incrementa, la función complejidad es monótona creciente (f(n) >f(m) , n>m)con

1.2 ARITMETICA DE LA NOTACIÓN 0La notación O (también llamada O mayúscula), se utiliza para comparar la eficiencia de los algoritmos.
Tipos de análisis de la Notacion O
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 del peor caso
¿Cuál es el tiempo que necesitaría un algoritmo concreto?
•oVaría en función del ordenador que utilicemos
oVaría en función del compilador que seleccionemos.
oPuede 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 (log n), es más eficiente que un algoritmo O(n),
Un algoritmo O(n),es más eficiente que un algoritmo O(n log n),
Un algoritmo O(n log n), es mas eficiente que un algoritmo O (n2),
Un algoritmo O (n2), es más eficiente que un algoritmo O(n3),
Un algoritmo O (n3), es más eficiente que un algoritmo O (2n).
-------------------------------------------------
Propiedades de la notación O
-------------------------------------------------
O(f(n)) = O(f(n))
O...