Re: [其他] 一題FFT....(傅立葉轉換)
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
推
12/25 01:06, , 1F
12/25 01:06, 1F
→
12/25 01:06, , 2F
12/25 01:06, 2F
推
12/25 01:21, , 3F
12/25 01:21, 3F
→
12/25 01:22, , 4F
12/25 01:22, 4F
→
12/25 08:49, , 5F
12/25 08:49, 5F
推
12/25 10:39, , 6F
12/25 10:39, 6F
討論串 (同標題文章)
完整討論串 (本文為第 1 之 2 篇)：