COMPLEJIDAD DE LOS ALGORITMOS
Enviado por rmezar • 26 de Septiembre de 2011 • 607 Palabras (3 Páginas) • 1.516 Visitas
COMPLEJIDAD DE LOS ALGORITMOS
La complejidad de los algoritmos nos representa o dice el tiempo de ejecución de cualquier programa en base a los 'n' datos de entrada. Por lo tanto la complejidad de cualquier algorito se expresa en los siguientes términos:
T(n) Funcion de la complejidad
la cual se interpreta de la siguiente manera:
El tiempo de ejecución está dado por los n datos de entrada
REGLAS PARA EL CALCULO DE LA COMPLEJIDAD DE UN ALGORITMO
1. El tiempo de ejecución de cada sentencia simple puede tomarse como complejidad de T(1)
2. Para las sentencias de bifurcación (if, case) el resultante de la complejidad será T(1)
3. La complejidad para los bucles (for, repeat, while) independientes será T(n)
4. La complejidad para los bucles anidados será: T(nm) donde m nos representa el numero de bucles anidados
Ejemplo 1:
El algoritmo a1 tarda n segundos en resolver un problema para una determinada cantidad de datos mientras que el algoritmo n
a1
a2
5n2
>=
n2+400n
4n2
>=
400n
n2
>=
100n
n
>=
100
n
<
100
a1 es mejor
n
>=
100
a2 es mejor
Ejemplo 2:
Dado el siguiente algoritmo determine su complejidad
INICIO
T(1)
Leer a,b,c,sum
T(1)
if a>3 then b=c*a
T(1)
desde a=1 hasta b
T(n)
sum=sum+a
T(1)
Fin
T(1)
FINAL
T(1)
La complejidad del algoritmo es T(n)
Análisis de Eficiencia de los
Algoritmos
Page 2
Indice
• Introducción
• Midiendo la Eficiencia de los Algoritmos
• Notación Asintótica
• Reglas para el Cálculo de la Eficiencia de los Algoritmos
– Funciones no recursivas
– Funciones Recursivas
• Solución de Ecuaciones de Recurrencia
– Sustitución
– Inducción
– Árbol de Recursión
– Fórmula Maestra
– Ecuación Característica
Introducción
• Objetivo: analizar la eficiencia de un algoritmo en función del
tamaño de la entrada.
• Ventajas:
– Mejor Comprensión de los algoritmos
– Diseñar algoritmos mejores
– Determinas la escalabilidad
• Depende
– El problema que tratamos de resolver
– El lenguaje de programación utilizado
– El compilador
– El hardware utilizado
– La habilidad del programador
Análisis de Eficiencia
• Empírica
• Teórica
estamos interesados en contar cuantas instrucciones
simples (asignaciones, comparaciones, etc.) se ejecutan,
asumimos que independientemente de la máquina en
que se ejecute, todas las operaciones simples
consumen el mismo tiempo.
Principio de Invarianza:
Dos implementaciones distintas de un mismo algoritmo
no difieren en eficiencia más que en una constante
multiplicativa.
Tipos de Análisis
• Peor de los Casos:Se corresponde con el peor tiempo. T(n)
es el tiempo máximo sobre las entradas.
• Mejor Caso: Límite inferior en el tiempo. T(n) es el menor
tiempo de todas las posibles entradas
• Caso Promedio: Es el tiempo medio esperado sobre todas
las posibles entradas de tamaño n. Se considera una
distribución de probabilidad sobre las entradas.
• Análisis Probabilístico: Es el tiempo de ejecución esperado
para una entrada aleatoria. Se expresa tanto el tiempo de
ejecución y la probabilidad de obtenerlo.
• Análisis Amortizado: El tiempo que se obtiene para un
conjunto de ejecuciones, dividido por el número de
ejecuciones.
Notación Asintótica
• Estudia el comportamiento del algoritmo cuando el tamaño
de las entradas, n, es lo suficientemente grande, sin tener
...