¿Cuál es la complejidad del algoritmo de Horner si encontramos P (x) calculando cada término del polinomio desde cero?

Aprovecharé la respuesta de Han, pero utilizaré un enfoque diferente para medir la complejidad. Deje que la complejidad se mida como el número de sumas, siendo la multiplicación una suma por cada 1 en una representación binaria del multiplicador. Esto supone un cambio y un enfoque adicional para la multiplicación de la máquina. Supongamos que, en promedio, un número binario tendrá la mitad de sus dígitos establecidos en 1. Supongamos que, en promedio, los coeficientes del polinomio yx tienen 32 bits de longitud, es decir, medio entero doble. Por lo tanto, la multiplicación será en promedio 16 veces más compleja que la suma.

Evaluar el polinomio un término a la vez desde cero tiene una complejidad de n adiciones más (n ^ 2 + n) / 2 multiplicaciones, es decir, una complejidad de 8n ^ 2 + 9n adiciones.

La evaluación utilizando el método de Horner requiere n adiciones más n multiplicaciones, es decir, una complejidad de 17n adiciones.

Por lo tanto, el método Honer reduce la complejidad en un factor de 8n / 17 + 9/17, que se aproxima a un factor de reducción de la complejidad de (n + 1) / 2