本章涉及知識點(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次加法
