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.

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)

                  }