复杂度 求解方程,计算a T(n)=27(m2)+n) →7(m)=6nlgn 7-1 od o o a-1 说明 定理 y=Vna,其中Vn是 Vandermonde矩阵x 对于任意k=0 的取值为an的幂次方 于是 第K)位置的 数是n a=DFT(y)=V1(y) 证明:如右图计 当时为1否则 结论 计算方法 利用FFT思想,我们同样可以得到复杂度为 e(nlgn)的快速计算方法 ∑yn 66 复杂度 • T(n)=2T(n/2)+θ(n) • ÎT(n)= θ(n lgn) 求解方程，计算a 说明 • y = Vna, 其中 Vn 是 Vandermonde 矩阵其x 的取值为 ωn 的幂次方 • 于是 • a＝DFTn -1(y)＝Vn -1(y) 定理 • 对于任意 j, k = 0, 1, . . . , n - 1, Vn -1 第 (j, k) 位置 的 数是 ωn -jk/n. • 证明：如右图计 算Vn -1Vn=I可得： • 当j=j’时为1否则 为0。 结论 计算方法 • 利用FFT思想，我们同样可以得到复杂度为 θ(n lg n)的快速计算方法