Re: [其他] 一題FFT....(傅立葉轉換)

[suhorng ( )]

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
推 bernachom   : 很詳細的說明，不過我要看一下...反應沒你這麼好
→ bernachom   :謝謝教導了。
推 bernachom   :不好意思，另外請教一下，a.b.c小題是算在一起的嗎?
→ bernachom   :有辦法區分一下嗎，謝謝幫忙
→ suhorng     :我算一下, 晚上回來修文修得清楚點 XD""
推 bernachom   :謝謝您^^