一個優(yōu)化的低階多項式累加和問題求解算法

劉瀚文

摘要： 本文針對低階多項的多項式累加和問題∑〖DD（〗n〖〗k=1〖DD）〗f（k），其中f（x）=c0+c1x+…+cm-1xm-1+cmxm，當(dāng)多項式冪次m較小，累加項數(shù)n較大的情況下，根據(jù)二分求解思想，設(shè)計了一種高效的遞推求解方法，其時間復(fù)雜度為O（m2log n），而采用Horner格式計算多項式在每點(diǎn)的取值，再進(jìn)行累加的樸素算法時間復(fù)雜度為O（mn），從而解決了在n[JP8]>>[JP]m時，大大提高了低階多項的多項式累加求和的效率。

關(guān)鍵詞： 多項式求值； 多項式累加和問題； Horner格式； 冪和問題

中圖分類號：TP391.7

文獻(xiàn)標(biāo)志碼： A

文章編號： 2095-2163（2017）05-0073-04

引言

在數(shù)論的世界中，對于多項式的相關(guān)性質(zhì)研究是一個亙古不變的課題，吸引著一代又一代的專家和學(xué)者對其展開求知與探索。多項式求和問題是數(shù)論中的基礎(chǔ)問題，在氣象預(yù)報、生物計算等許多場景中有著重要應(yīng)用。本文針對低階多項的多項式累加和問題，即當(dāng)多項式冪次m較小，累加項數(shù)n較大的情況下，根據(jù)二分求解思想，設(shè)計了一種高效的遞推求解方法，重點(diǎn)解決了當(dāng)n[JP8]>>[JP]m時，關(guān)于低階多項的多項式累加求和的效率能夠獲得大幅提升的問題。而且仿真運(yùn)行結(jié)果表明，該方法要明顯優(yōu)于傳統(tǒng)的Horner算法。

方向進(jìn)行推算，因此問題的空間復(fù)雜性為O（m）；[JP]而基于上述分析，可知對于任意給定的正整數(shù)n，上述折半方式的遞推次數(shù)為O（log n），因此，∑〖DD（〗n〖〗k=1〖DD）〗f（k）的計算可以在O（m2log n）時間內(nèi)完成。而通用的Horner樸素算法時間復(fù)雜度為O（mn），這就解決了當(dāng)n[JP8]>>[JP]m時，大大提高了低階多項的多項式累加求和效率的研究課題。

[參考文獻(xiàn)

BARBEAU E J. Polynomials[M]. New York： Springer-Verlag， 1989.

[2] KNUTH D E. The art of computer programming（Sorting and Searching）[M]. 2nd ed. New Jersey：Addison-Wesley professional， 1998.

[3] Wikipedia. Polynomial[EB/OL]. [2017-08-21]. https：//en.wikipedia.org/wiki/Polynomial.

[4] SAUER T. 數(shù)值分析[M]. 2版. 裴玉茹， 馬賡宇，譯. 北京：機(jī)械工業(yè)出版社，2014.

[5] GREENBAUM A， CHARTIER T P. 數(shù)值方法：設(shè)計、分析和算法實(shí)現(xiàn)[M]. 吳兆金，王國英，范紅軍，譯. 北京：機(jī)械工業(yè)出版社，2016.

[6] HORN R A， JOHNSON C R. 矩陣分析[M]. 2版. 張明堯， 張凡，譯. 北京：機(jī)械工業(yè)出版社，2014.endprint