一个优化的低阶多项式累加和问题求解算法

摘要：

本文针对低阶多项的多项式累加和问题∑n k=1 f(k),其中f(x)=c0+c1 x+…+cm-1 xm-1+cm xm,当多项式幂次m较小,累加项数n较大的情况下,根据二分求解思想,设计了一种高效的递推求解方法,其时间复杂度为O(m2 log n),而采用Horner格式计算多项式在每点的取值,再进行累加的朴素算法时间复杂度为O(mn),从而解决了在n>>m时,大大提高了低阶多项的多项式累加求和的效率.

关键词：多项式求值、多项式累加和问题、Horner格式、幂和问题

所属期刊栏目：7

分类号：TP391.7(计算技术、计算机技术)

在线出版日期：2017-11-16（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：73-75,78