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