美文网首页
霍纳法则(Horner Rule)--计算多项式的值

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

作者: CODERLIHAO | 来源:发表于2020-07-09 20:27 被阅读0次

    假设有n+1个实数a0,a1,…,an,和x的序列,要对多项式Pn(x)= anxn +an-1xn-1+…+a1x+a0求值,直接方法是对每一项分别求值,并把每一项求的值累加起来,这种方法十分低效,时间复杂度O(nk)。
    有没有更高效的算法呢?答案是肯定的。通过如下变换我们可以得到一种快得多的算法,即
    Pn(x)= anxn +an-1xn-1+…+a1x+a0=((…(((anx +an-1)x+an-2)x+ an-3)…)x+a1)x+a0
    这种求值的方法我们称为霍纳法则
    比如
    Pn(x) = 2x4 -x3 - 3x2 + x - 5
    Pn(x) = x(2x3 -x2 - 3x+ 1) - 5
    Pn(x) = x(x(2x2 -x - 3)+ 1) - 5
    Pn(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));
    

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


    image.png

    相关文章

      网友评论

          本文标题:霍纳法则(Horner Rule)--计算多项式的值

          本文链接:https://www.haomeiwen.com/subject/gbascktx.html