Page 33 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

Visto así, tenemos una función de recurrencia

T(n) = O (1) + T(n / 2),

cuya solución es
O (log n).

Insertado el método auxiliar potencia en el método evaluaPolinomio, la complejidad compuesta es
del orden O (n log n), al multiplicarse por N un subalgoritmo de O (log n).

Opción C: División sintética

Para calcular el valor del polinomio se puede utilizar la división. El residuo de la división es el valor
P(x). Por ejemplo, si el polinomio a calcular es P(x) = 3x – 2x + x – 6, para x = 2, la división será:
2
3

Por tanto, P (2) = –4.

Como se aprecia, se debe dividir frecuentemente el polinomio entre el binomio (x – a) para conocer
el residuo, es ineficiente calcular cada uno de los k+1 términos separadamente y luego sumarlos.
Esto indica n adiciones y n(n + 1) /2 multiplicaciones. Por ende, para simplificar el proceso, se usará
el criterio de la división sintética que consiste en lo siguiente:

Si

Q(X)= A X + A X + A X + … A X + A ,
n-1
n-3
n-2
0 2 n-2 n-1
y R es el residuo que resulta de dividir el polinomio
P(X)= a X + a X + a X + ..... +a
n
n-1
n-2
0 1 2 n
entre el binomio X-a, entonces:
P(X)= (X - a) Q(X) + R
o sea,

a X + a X + a X + ... a = A X + (A - a A ) X + ... + (R - a A )
n-1
n-1
n
n-2
n
0 1 2 n o 1 0 n-1
27