拉格朗日插值公式以及一些變形
拉格朗日插值公式看起來很復(fù)雜寻馏，其實(shí)自己舉一個(gè)例子解一解就很容易明白了吱瘩。讀書的過程中發(fā)現(xiàn)裙秋，越是歸結(jié)為簡單形式的式子容燕，用計(jì)算機(jī)編程實(shí)現(xiàn)起來越容易梁呈，優(yōu)化的地方也就越多；舉完例子發(fā)現(xiàn)蘸秘，這玩意如果式子長了的話官卡，還真不是人解的……
跟我們的目標(biāo)接近一下（我們的目標(biāo)是求C(x)，且C(x)=A(x)*B(x)）醋虏，那么對A,B的任意一點(diǎn)(xk,yk)寻咒，都有C(xk)=A(xk)*B(xk)。
所以颈嚼，想求兩個(gè)多項(xiàng)式的乘積的時(shí)候毛秘，除了直接用系數(shù)表達(dá)來求，還可以用點(diǎn)值表達(dá)來求：
先求出A(x)阻课、B(x)的點(diǎn)值表達(dá)叫挟，再相乘。這個(gè)過程需要O(n)限煞。再將點(diǎn)值表達(dá)插值轉(zhuǎn)成系數(shù)表達(dá)需要O(n^2)抹恳。
乍一看和前面描述的直接用系數(shù)表達(dá)求得結(jié)果的復(fù)雜度一樣，都是O(n^2)的署驻。實(shí)際上奋献，點(diǎn)值表達(dá)中取點(diǎn)可以影響計(jì)算。用FFT可以將復(fù)雜度降到O(nlgn)旺上。
