Método de Horner para evaluación de polinomios

Dado un polinomio de la forma c n x n + c n-1 x n-1 + c n-2 x n-2 + … + c 1 x + c 0 y un valor de x, encuentre el valor del polinomio para a valor dado de x. Aquí c n , c n-1 , .. son números enteros (pueden ser negativos) y n es un número entero positivo.
La entrada tiene la forma de una array, digamos poly[], donde poly[0] representa el coeficiente para x n y poly[1] representa el coeficiente para x n-1 y así sucesivamente.
Ejemplos: 

// Evaluate value of 2x3 - 6x2 + 2x - 1 for x = 3
Input: poly[] = {2, -6, 2, -1}, x = 3
Output: 5

// Evaluate value of 2x3 + 3x + 1 for x = 2
Input: poly[] = {2, 0, 3, 1}, x = 2
Output: 23

Una forma ingenua de evaluar un polinomio es evaluar uno por uno todos los términos. Primero calcule x n , multiplique el valor por c n , repita los mismos pasos para otros términos y devuelva la suma. La complejidad temporal de este enfoque es O(n 2 ) si usamos un ciclo simple para la evaluación de x n . La complejidad del tiempo se puede mejorar a O(nLogn) si usamos el enfoque O(Logn) para la evaluación de x n .
El método de Horner se puede utilizar para evaluar polinomios en tiempo O(n). Para comprender el método, consideremos el ejemplo de 2x 3 – 6x 2 + 2x – 1. El polinomio se puede evaluar como ((2x – 6)x + 2)x – 1. La idea es inicializar el resultado como coeficiente de x norteque es 2 en este caso, multiplique repetidamente el resultado con x y agregue el siguiente coeficiente al resultado. Finalmente devuelve resultado.
A continuación se muestra la implementación del método de Horner. 
 

C++

#include <iostream>
using namespace std;
 
// returns value of poly[0]x(n-1) + poly[1]x(n-2) + .. + poly[n-1]
int horner(int poly[], int n, int x)
{
    int result = poly[0]; // Initialize result
 
    // Evaluate value of polynomial using Horner's method
    for (int i=1; i<n; i++)
        result = result*x + poly[i];
 
    return result;
}
 
// Driver program to test above function.
int main()
{
    // Let us evaluate value of 2x3 - 6x2 + 2x - 1 for x = 3
    int poly[] = {2, -6, 2, -1};
    int x = 3;
    int n = sizeof(poly)/sizeof(poly[0]);
    cout << "Value of polynomial is " << horner(poly, n, x);
    return 0;
}

Java

// Java program for implementation of Horner Method
// for Polynomial Evaluation
import java.io.*;
 
class HornerPolynomial
{
    // Function that returns value of poly[0]x(n-1) +
    // poly[1]x(n-2) + .. + poly[n-1]
    static int horner(int poly[], int n, int x)
    {
        // Initialize result
        int result = poly[0]; 
  
        // Evaluate value of polynomial using Horner's method
        for (int i=1; i<n; i++)
            result = result*x + poly[i];
  
        return result;
    }
     
    // Driver program
    public static void main (String[] args)
    {
        // Let us evaluate value of 2x3 - 6x2 + 2x - 1 for x = 3
        int[] poly = {2, -6, 2, -1};
        int x = 3;
        int n = poly.length;
        System.out.println("Value of polynomial is "
                                        + horner(poly,n,x));
    }
}
 
// Contributed by Pramod Kumar

Python3

# Python program for
# implementation of Horner Method
# for Polynomial Evaluation
 
# returns value of poly[0]x(n-1)
# + poly[1]x(n-2) + .. + poly[n-1]
def horner(poly, n, x):
 
    # Initialize result
    result = poly[0] 
  
    # Evaluate value of polynomial
    # using Horner's method
    for i in range(1, n):
 
        result = result*x + poly[i]
  
    return result
  
# Driver program to
# test above function.
 
# Let us evaluate value of
# 2x3 - 6x2 + 2x - 1 for x = 3
poly = [2, -6, 2, -1]
x = 3
n = len(poly)
 
print("Value of polynomial is " , horner(poly, n, x))
 
# This code is contributed
# by Anant Agarwal.

C#

// C# program for implementation of
// Horner Method  for Polynomial Evaluation.
using System;
 
class GFG
{
    // Function that returns value of poly[0]x(n-1) +
    // poly[1]x(n-2) + .. + poly[n-1]
    static int horner(int []poly, int n, int x)
    {
        // Initialize result
        int result = poly[0];
 
        // Evaluate value of polynomial
        // using Horner's method
        for (int i = 1; i < n; i++)
            result = result * x + poly[i];
 
        return result;
    }
     
    // Driver Code
    public static void Main()
    {
        // Let us evaluate value of
        // 2x3 - 6x2 + 2x - 1 for x = 3
        int []poly = {2, -6, 2, -1};
        int x = 3;
        int n = poly.Length;
        Console.Write("Value of polynomial is "
                            + horner(poly,n,x));
    }
}
 
// This code Contributed by nitin mittal.

PHP

<?php
// PHP program for implementation
// of Horner Method for Polynomial
// Evaluation.
 
// returns value of poly[0]x(n-1) +
// poly[1]x(n-2) + .. + poly[n-1]
function horner($poly, $n, $x)
{
    // Initialize result
    $result = $poly[0];
 
    // Evaluate value of polynomial
    // using Horner's method
    for ($i = 1; $i < $n; $i++)
        $result = $result *
                  $x + $poly[$i];
 
    return $result;
}
 
// Driver Code
 
// Let us evaluate value of
// 2x3 - 6x2 + 2x - 1 for x = 3
$poly = array(2, -6, 2, -1);
$x = 3;
$n = sizeof($poly) / sizeof($poly[0]);
 
echo "Value of polynomial is ".
         horner($poly, $n, $x);
 
// This code is contributed by mits.
?>

Javascript

<script>
// Javascript program for implementation
// of Horner Method for Polynomial
// Evaluation.
 
// returns value of poly[0]x(n-1) +
// poly[1]x(n-2) + .. + poly[n-1]
function horner(poly, n, x)
{
 
    // Initialize result
    let result = poly[0];
 
    // Evaluate value of polynomial
    // using Horner's method
    for (let i = 1; i < n; i++)
        result = result *
                  x + poly[i];
 
    return result;
}
 
// Driver Code
 
// Let us evaluate value of
// 2x3 - 6x2 + 2x - 1 for x = 3
let poly = new Array(2, -6, 2, -1);
let x = 3;
let n = poly.length
 
document.write("Value of polynomial is " +
         horner(poly, n, x));
 
// This code is contributed by _saurabh_jaiswal.
</script>

Producción: 
 

Value of polynomial is 5

Complejidad de tiempo : O(n)

Espacio auxiliar: O(1)
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *