假设有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
网友评论