一個(gè)優(yōu)化的低階多項(xiàng)式累加和問(wèn)題求解算法

劉瀚文

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

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

中圖分類號(hào)：TP391.7

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

文章編號(hào)： 2095-2163（2017）05-0073-04

引言

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

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

[參考文獻(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è)計(jì)、分析和算法實(shí)現(xiàn)[M]. 吳兆金，王國(guó)英，范紅軍，譯. 北京：機(jī)械工業(yè)出版社，2016.

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