霍纳法则(Horner Rule)--计算多项式的值

假设有n+1个实数a₀，a₁，…，a_n,和x的序列，要对多项式P_n(x)= a_nxⁿ +a_n-1x^n-1+…+a₁x+a₀求值，直接方法是对每一项分别求值，并把每一项求的值累加起来，这种方法十分低效，时间复杂度O(n^k)。
有没有更高效的算法呢?答案是肯定的。通过如下变换我们可以得到一种快得多的算法，即
P_n(x)= a_nxⁿ +a_n-1x^n-1+…+a₁x+a₀=((…(((a_nx +a_n-1)x+a_n-2)x+ a_n-3)…)x+a₁)x+a₀
这种求值的方法我们称为霍纳法则
比如
P_n(x) = 2x⁴ -x³ - 3x² + x - 5
P_n(x) = x(2x³ -x² - 3x+ 1) - 5
P_n(x) = x(x(2x² -x - 3)+ 1) - 5
P_n(x) = x(x(x(2x -1) - 3)+ 1) - 5
这样时间复杂度就变成O(n)了。

    function horner(a,x) {
        let length = a.length;
        //获取最高阶的系数
        let temp  = a[0];
        for (let i = 1; i < length; i++) {
            temp = x * temp + a[i];
        }
        return temp
    }

    function stupid(a,x){
        let length = a.length;
        let temp = 0;
        for (let i = 0; i < length; i++) {
            temp += a[i] * Math.pow(x,length-1-i);
        }
        return temp
    }

    let a = [1,4,2,1,4,2,1,4,2,1,4,2,1,4,2,1,4,2,1,4,2,1,4,2,1,4,2,1,4,2,1,4,2,1,4,2,1,4,2,1,4,2,1,4,2,1,4,2,1,4,2,1,4,2,1,
        4,2,1,4,2,1,4,2,1,4,2,1,4,2,1,4,2,1,4,2,1,4,2,1,4,2,1,4,2,1,4,2,1,4,2,1,4,2,1,4,2];
    let x = 3;

    let start =  Date.now();
    for (let i = 0; i <1000000; i++) {
        horner(a,x);
    }
    console.log("horner time = ",(Date.now() - start));

    start =  Date.now();
    for (let i = 0; i <1000000; i++) {
        stupid(a,x);
    }
    console.log("stupid time = ",(Date.now() - start));

两个计算结果有着巨大的差异