Avaliar polinômios de grau n em tempo linear

Antes de iniciar a resposta, propriamente dita:

1. Avaliar um polinômio p(x) significa, calcular qual o valor de p dado um valor para x como entrada;

2. Como o polinômio tem grau n, então os coeficientes de cada termo da soma estão armazenados no vetor coef, de modo que coef[0] é o valor do coeficente a0 (aquele que não tem x multiplicando ele);

3. Note que existe a posição coef[n] no vetor e, portanto, o mesmo deve ter espaço para pelo menos n+1 variáveis do tipo double.

4. Exemplo: o polinômio p(x) = 3x^2 -5x +2 tem seus coeficientes armazenados no vetor coef assim: (2, -5, 3). Ou seja, coef[0] = 2, coef[1] = -5 e coef[2] = 3. Neste exemplo, se escolhermos x = -1, o valor de p(-1) será 10. Se escolhermos x = 2, então p(2) = 4.

Vamos ao código agora:

double avalia_polinomio(int n, double coef[], double x) {

  int i;

  double p = 0.0;

  for ( i = n; /* A */ i >= 0; i-- ) {

      p = p * x + coef[i];

  }

  return p;

}

O código está correto. Qual seria uma boa invariante A para demonstrar isso? Consulte http://mathworld.wolfram.com/HornersRule.html para saber mais.

O código tem complexidade de tempo linear sobre n, o grau do polinômio p. Para verificar isto, basta perceber que o laço executa n+1 vezes e, dentro dele, só existem operações de tempo constante.