TEMA 1
EFISIENCIA DE ALGORITMO
INTRODUCCIÓN
En un sentido amplio, dado un problema y un dispositivo donde resolverlo, es Necesario proporcionar un método preciso que lo resuelva, adecuado al dispositivo.
A tal método lo denominamos algoritmo.
EFICIENCIA Y COMPLEJIDAD
Una vez dispongamos de un algoritmo que funciona correctamente, es necesario definir criterios para medir su rendimiento o comportamiento. Estos criterios se centran principalmente en su simplicidad y en el uso eficiente de los recursos.
se piensa que un algoritmo sencillo no es muy eficiente. Sin embargo, la sencillez es una característica muy interesante a la hora de diseñar un algoritmo, pues facilita su verificación, el estudio de su eficiencia y su mantenimiento. De ahí que muchas veces prime la simplicidad y legibilidad del código frente a alternativas más crípticas y eficientes del algoritmo.
Ejemplo:
función multiplica (X,Y,n) Eficiencia
{
if (P es pequeño) { O(1)
return X*Y; O(1)
} else {
Obtener xi, xd, yi, yd; O(n)
z1 = multiplica (xi, yi, n/2); T(n/2)
z2 = multiplica (xi, yd, n/2); T(n/2)
z3 = multiplica (xd, yi, n/2); T(n/2)
z4 = multiplica (xd, yd, n/2); T(n/2)
aux = suma(z2,z3); O(n)
z1 = desplaza_izq(z1,n); O(n)
aux = desplaza_izq(aux,n/2); O(n)
z = suma(z1,aux); O(n)
z = suma(z,z4); O(n)
return z; O(1)
}
}