A(x) = 1 - 3x B(x) = 2 + 4x y = C(x) = A(x)B(x) 為二次式 直接計算 C(x) 的話時間複雜度為 O(n^2) 但 y = C(x) = A(x)B(x) 為 2 次式, 只要 3 個點就能決定 C(x) 也就是假設我們任取三個點 x_1, x_2, x_3 (兩兩不相等) 則 C(x) 可以用 (x_1, C(x_1)), (x_2, C(x_2)), (x_3, C(x_3)) 決定 但 y = C(x) = A(x)B(x), 因此 C(x_1) = A(x_1)B(x_1) C(x_2) = A(x_2)B(x_2) C(x_3) = A(x_3)B(x_3) 假設我們已經求出 A(x_1), A(x_2), A(x_3)、B(x_1), B(x_2), B(x_3) 那求出 C(x_1), C(x_2), C(x_3) 只要 O(n) 的時間 所以現在的重點 考慮如何有效率的求出 A(x_1)~A(x_3), B(x_1)~B(x_3) 以及從 C(x_1)~C(x_3) 算出 C(x) 這個題目就是要你用 DFT 去算上面兩行 至於擴展成 4 個是因為這樣剛好是 2 的冪次, 否則不知道要怎麼算 觀察 1 的 n 次方根的特性 e^(2πik/n), k = 0 , 1 , ... , n－1 令 ω_n 代表 e^(2πi/n) , 觀察到對於正偶數的 n, 有 [ (ω_n)^k ]^2 = [ (ω_n)^(k+n/2) ]^2, 因此在求值的時候, 若我們所選的點為 (ω_n)^0, (ω_n)^1, (ω_n)^2, ..., (ω_n)^{n-1} 把係數的奇偶項分開來遞迴下去, 再用 O(n) 的時間求出來這層遞迴原本的值, 則總時間複雜度為 T(n) = 2T(n/2)＋O(n) = O(n log n). 虛擬碼如 http://www.cs.uwaterloo.ca/~kogeddes/cs487/LectureMaterials/Chapter_4_Materials/FFTalgorithm.pdf (縮 http://0rz.tw/TjHDo ) 或 http://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm 。 對不起我自己沒有詳細研究過 DFT 及 DFT^(-1), 只能粗淺說一下我的理解... 唔 至於如果已經求出 n 個點的值 y_0, y_1, ..., y_{n-1} (用ω_n^0 ~ ω_n^{n-1}) 則可求出多項式 f(x) = a_0 + a_1x + a_2x^2 + ... + a_{n-1}x^{n-1} 係數為 1 n-1 a_j = ---Σ y_k(ω_n)^(-kj) n k=0 因此也可以用跟 DFT 差不多的方法來算, 變數位置換了而已 (就是最後說 a 和 y 的角色交換, ω_n 改成 (ω_n)^{-1} 那邊 ※ 引述《bernachom (Terry)》之銘言： : 請教一題.. : http://ppt.cc/(i27 : 應該是算很基本的題目，可是看課本就是看不太懂應該要怎麼算.. : 麻煩前輩們指導一下了 : 謝謝幫忙。 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.217.35.222