卷別

資料結構與演算法

選擇

國立臺灣大學 2026 · 考試 · 第 9 題

(4 points) Which property of the root of unity $W_n = e^{2\pi i / n}$ , where $n$ is a power of 2, allows the Cooley–Tukey fast-fourier transform algorithm to achieve its speedup in time complexity?

(A)
The Magnitude Property: $|W_n^k| = 1$ for all $k$ .
(B)
The Symmetry Property: $W_n^{k + n/2} = -W_n^k$ , allowing dividing the problem into even/odd sub-problems.
(C)
The Orthogonality Property: The sum of all roots $\sum_{k=0}^{N-1} W_n^k = 0$ .
(D)
The Conjugate Property: $W_n^{n-k} = \overline{W_n^{k}}$ .
(E)
The Count Property: There are exactly $n$ unique roots $W_n^k$ across all $k$ .

標準解析

AI 已複查