本章涉及知識點(diǎn)
1虫埂、多項(xiàng)式計(jì)算式
2耕突、如何在1毫秒內(nèi)計(jì)算出多項(xiàng)式結(jié)果
3、秦九韶算法
4俊柔、改善程序算法
一君丁、多項(xiàng)式計(jì)算式
假設(shè)我們有如下計(jì)算式枫夺,求當(dāng)x=2時(shí)f(x)的值
這是一個(gè)一元n次多項(xiàng)式,涉及到的四則運(yùn)算包含加法和乘法绘闷,我們的需求是盡可能在1毫秒之內(nèi)計(jì)算出其結(jié)果
二橡庞、如何在1毫秒內(nèi)計(jì)算出多項(xiàng)式結(jié)果
直觀上想到的第一種方法就是直接帶入x=2運(yùn)算即可,下面為了演示計(jì)算的消耗時(shí)間印蔗,我們用JavaScript語言作為計(jì)算演示(當(dāng)然扒最,不限于任何語言來演示)
為了盡快計(jì)算結(jié)果,我們可以分析出程序要盡量減少調(diào)用API
為此我們編寫出如下程序
代碼中除了調(diào)用console.log方法耗時(shí)喻鳄,并沒有調(diào)用其余API函數(shù)扼倘,我們帶入x=2直接計(jì)算出結(jié)果
可以看到程序運(yùn)行大約2毫秒,多運(yùn)行幾次除呵,大概需要2~3毫秒之間再菊,偶爾會出現(xiàn)1毫秒,顯然不符合我們的需求
那么問題出在哪里呢颜曾?我們已經(jīng)盡可能減少API的調(diào)用纠拔,所以我們需要聚焦到f(x)多項(xiàng)式本身
觀察f(x),發(fā)現(xiàn)這個(gè)多項(xiàng)式進(jìn)行了4次加法操作泛豪,那么乘法的次數(shù)呢稠诲?進(jìn)行了7+6+4+1=18次乘法,在計(jì)算機(jī)里诡曙,乘法的本質(zhì)就是加法臀叙,且乘法的耗時(shí)要大于加法,那么自然而然我們只有降低乘法的次數(shù)价卤,才能提高f(x)的計(jì)算速度
三劝萤、秦九韶算法
我們抽象出一般的一元多項(xiàng)式
容易計(jì)算出,f(x)進(jìn)行了n次加法計(jì)算慎璧,進(jìn)行的乘法計(jì)算次數(shù)為等差數(shù)列的求和:
顯然床嫌,f(x)乘法的計(jì)算次數(shù)要遠(yuǎn)遠(yuǎn)大于加法的計(jì)算次數(shù)跨释,我們需要利用我國南宋時(shí)期著名數(shù)學(xué)家秦九韶算法進(jìn)行多項(xiàng)式等效變形
秦九韶算法使用提取x公因式和整體換元法來等效的變形了f(x),而經(jīng)過算法變形之后厌处,我們可以看到f(x)的乘法計(jì)算次數(shù)降低到了n次
這樣對于n次多項(xiàng)式的求值為題鳖谈,就轉(zhuǎn)化為n個(gè)一次多項(xiàng)式的求值問題,妙哉阔涉!
四缆娃、改善程序算法
我們明白了需要問題的關(guān)鍵是要降低乘法計(jì)算次數(shù),利用秦九韶算法洒敏,我們做如下變形f(x)
修改程序?yàn)?/p>
減少了乘法計(jì)算次數(shù)龄恋,程序的計(jì)算速度也提高了
最后我們可以根據(jù)秦九韶算法總結(jié)出:對于一個(gè)n次多項(xiàng)式,至多做n次乘法和n次加法