Complejidad

Complejidad Computacional
Análisis Comparativo de la Evaluación de Polinomios empleando el Método de Horner vs. el Tradicional Método de Potenciación
Lic. Adriana Labra Barrios. M. en C. Eduardo René Rodríguez Ávila. Sección de Estudios de Posgrado e Investigación UPIICSA

Abstracto.
Este artículo presenta un análisis comparativo entre dos métodos de evaluación de expresiones polinómicas. Elprimero corresponde a la forma tradicional (o directa) de evaluación y que implica el cálculo de las respectivas potencias de los términos de la expresión. El segundo método considerado es conocido como el Método de Horner, en el que se reorganiza el polinomio a manera de una serie de multiplicaciones anidadas de forma que no puedan evaluarse potencias mayores a una. El objetivo del análisis espresentar el costo computacional asociado a ambos métodos para así determinar cuál es más eficiente bajo un criterio completamente cuantitativo. Una introducción al tema de la complejidad computacional es presentado y conclusiones con respecto al uso de recursos de cómputo son incluidas.

Polinomios.
Un polinomio es una expresión formada por la suma de múltiplos de potencias de una variableindependiente. Por ejemplo:

3x4+5x3+7x2-2x+5.

(1)

Cada una de los elementos unidos por operaciones de suma o resta son llamados términos y el factor multiplicativo en cada término denominado coeficiente. El último elemento del polinomio, que no incluye a una variable, recibe el nombre de término constante debido a que implica la multiplicación de la variable independiente elevada a lapotencia de cero. El grado del polinomio queda determinado por el término de potencia mayor. El nombre del polinomio queda determinado por la cantidad de términos que lo forman. Un polinomio con un sólo término se llama monomio, contando con dos términos es un binomio, si cuenta con tres es un trinomio y así sucesivamente, aunque en la práctica se suele denominar polinomio a toda expresión de tres o mástérminos. De forma general, un polinomio P de grado n es expresado:
1

Pn(x)=anxn+an-1xn-1+an-2xn-2+...+a2x2+a1x+a0
y cuya evaluación puede ser considerada como:
n

(2)

Pn ( x ) = Â ai x i
i= 0

(3)

Método de evaluación directa o tradicional.
†
La forma de evaluación con la que seguramente estaremos más familiarizados consiste en efectuar el cálculo correspondiente a cadatérmino y sumando resultados parciales, reproduciendo lo representado por la ecuación 3. Si hemos de hablar del cálculo de este tipo de expresiones empleando un dispositivo de cómputo, entonces debemos poder contar con la posibilidad de efectuar las operaciones aritméticas implicadas, incluyendo la potenciación. Por supuesto, la mayoría de los microprocesadores para computadores de escritorio ysuperiores incluyen dentro de su repertorio de instrucciones aquellas necesarias para efectuar las operaciones aritméticas básicas incluyendo la potenciación. Todas estas debidamente soportadas por circuitería dedicada, esto es, la lógica de cada instrucción se encuentra “alambrada” permitiendo que sea ejecutada lo más rápidamente posible. El alambrar una instrucción implica un determinado costo, grado decomplejidad y consumo de energía. Los primeros microprocesadores incluían sólo instrucciones para las cuatro operaciones aritméticas elementales por lo que operaciones de potenciación debían realizarse mediante una serie de multiplicaciones sucesivas. Esto mismo aplica hoy en día con microprocesadores baratos y de bajo consumo de energía destinados a dispositivos portátiles o que no están pensadospara la realización de complejos cálculos matemáticos. Recurriremos a esta idea para nuestro análisis y retomaremos este punto más adelante.

Método de Horner.
El método de Horner es uno de esos “trucos” aritméticos y algebraicos a los que frecuentemente recurrían los programadores en las primeras décadas de la computación, y con los que buscaban hacer más eficiente un programa reduciendo...