秦九韶算法

本章涉及知識點(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)的值

一元n次多項(xiàng)式

這是一個(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

為此我們編寫出如下程序

直接計(jì)算f(x)

代碼中除了調(diào)用console.log方法耗時(shí)喻鳄,并沒有調(diào)用其余API函數(shù)扼倘,我們帶入x=2直接計(jì)算出結(jié)果

直接計(jì)算多項(xiàng)式結(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)式

一般化一元n次多項(xiàng)式

容易計(jì)算出,f(x)進(jìn)行了n次加法計(jì)算慎璧,進(jìn)行的乘法計(jì)算次數(shù)為等差數(shù)列的求和:

乘法計(jì)算次數(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)

秦九韶算法變形f(x)

修改程序?yàn)?/p>

秦九韶算法計(jì)算f(x)
秦九韶算法結(jié)果

減少了乘法計(jì)算次數(shù)龄恋,程序的計(jì)算速度也提高了

最后我們可以根據(jù)秦九韶算法總結(jié)出:對于一個(gè)n次多項(xiàng)式,至多做n次乘法和n次加法

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末凶伙,一起剝皮案震驚了整個(gè)濱河市郭毕,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌函荣,老刑警劉巖显押,帶你破解...
    沈念sama閱讀 223,002評論 6 519
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異傻挂,居然都是意外死亡乘碑,警方通過查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,357評論 3 400
  • 文/潘曉璐 我一進(jìn)店門金拒,熙熙樓的掌柜王于貴愁眉苦臉地迎上來兽肤,“玉大人,你說我怎么就攤上這事绪抛∽收。” “怎么了?”我有些...
    開封第一講書人閱讀 169,787評論 0 365
  • 文/不壞的土叔 我叫張陵幢码,是天一觀的道長笤休。 經(jīng)常有香客問我,道長症副,這世上最難降的妖魔是什么店雅? 我笑而不...
    開封第一講書人閱讀 60,237評論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮贞铣,結(jié)果婚禮上闹啦,老公的妹妹穿的比我還像新娘。我一直安慰自己辕坝,他們只是感情好窍奋,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,237評論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著,像睡著了一般费变。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上圣贸,一...
    開封第一講書人閱讀 52,821評論 1 314
  • 那天挚歧,我揣著相機(jī)與錄音,去河邊找鬼吁峻。 笑死滑负,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的用含。 我是一名探鬼主播矮慕,決...
    沈念sama閱讀 41,236評論 3 424
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼啄骇!你這毒婦竟也來了痴鳄?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 40,196評論 0 277
  • 序言:老撾萬榮一對情侶失蹤缸夹,失蹤者是張志新(化名)和其女友劉穎痪寻,沒想到半個(gè)月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體虽惭,經(jīng)...
    沈念sama閱讀 46,716評論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡橡类,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,794評論 3 343
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了芽唇。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片顾画。...
    茶點(diǎn)故事閱讀 40,928評論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖匆笤,靈堂內(nèi)的尸體忽然破棺而出研侣,到底是詐尸還是另有隱情,我是刑警寧澤疚膊,帶...
    沈念sama閱讀 36,583評論 5 351
  • 正文 年R本政府宣布义辕,位于F島的核電站,受9級特大地震影響寓盗,放射性物質(zhì)發(fā)生泄漏灌砖。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,264評論 3 336
  • 文/蒙蒙 一傀蚌、第九天 我趴在偏房一處隱蔽的房頂上張望基显。 院中可真熱鬧,春花似錦善炫、人聲如沸撩幽。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,755評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽窜醉。三九已至宪萄,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間榨惰,已是汗流浹背拜英。 一陣腳步聲響...
    開封第一講書人閱讀 33,869評論 1 274
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留琅催,地道東北人居凶。 一個(gè)月前我還...
    沈念sama閱讀 49,378評論 3 379
  • 正文 我出身青樓,卻偏偏與公主長得像藤抡,于是被迫代替她去往敵國和親侠碧。 傳聞我的和親對象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,937評論 2 361

推薦閱讀更多精彩內(nèi)容

  • 普通算法 f1(x) = a0 + a1x + a2x^2 + ... + an-1x^(n-1) + anx^n...
    Rush的博客閱讀 2,971評論 0 0
  • 算法和數(shù)據(jù)結(jié)構(gòu) [TOC] 算法 函數(shù)的增長 漸近記號 用來描述算法漸近運(yùn)行時(shí)間的記號缠黍,根據(jù)定義域?yàn)樽匀粩?shù)集$N=...
    wxainn閱讀 1,068評論 0 0
  • 首頁 資訊 文章 資源 小組 相親 登錄 注冊 首頁 最新文章 IT 職場 前端 后端 移動(dòng)端 數(shù)據(jù)庫 運(yùn)維 其他...
    Helen_Cat閱讀 3,891評論 1 10
  • 我會擁抱太陽不怕被那炙熱的太陽融化弄兜。 引用了一句歌詞來開始這篇文章,這是一個(gè)13歲的女孩寫的一首歌中的...
    浪噠閱讀 185評論 0 0
  • 引言 無數(shù)的狗主人目睹了家庭自制喂狗的好處嫁佳,比如清潔牙齒挨队、讓眼睛更明亮、讓毛發(fā)更有光澤蒿往、更瘦更有肌肉盛垦、讓身體脂肪更...
    朝酒暮歌閱讀 1,700評論 0 1