Biến đổi Fourier Nhanh 1D (Cooley-Tukey FFT) đệ quy thuần NumPy

Mục tiêu kiến thức

• Hiểu giải thuật Chia để trị (Divide and Conquer) trong Biến đổi Fourier Nhanh (FFT) độ phức tạp O(N log N).
• Phân tách chuỗi chẵn và chuỗi lẻ (Decimation in Time).
• Vector hóa thao tác cánh bướm (Butterfly Operation) với hệ số xoay (Twiddle Factors) số phức W_N^k = e^{-2π i k / N}.

Mô tả bài toán

Viết hàm fft_1d(x: np.ndarray) -> np.ndarray:

• x: Mảng 1D các số thực hoặc phức.
• Kiểm tra độ dài N = len(x):
• Nếu N không phải là lũy thừa của 2 (N ≤ 0 hoặc (N & (N - 1)) ≠ 0), raise ValueError("Do dai mang phai la luy thua cua 2").
• Điều kiện dừng đệ quy:
• Nếu N = 1, trả về chính mảng x.astype(np.complex128).
• Đệ quy:
• Phân tách: gọi đệ quy trên các phần tử chỉ số chẵn X_even = fft_1d(x[0::2]) và chỉ số lẻ X_odd = fft_1d(x[1::2]).
• Tính hệ số xoay cho nửa đầu k = 0, 1, …, N/2 - 1:

T_k = e^{-2π i k / N} · X_odd[k].

• Tổng hợp kết quả cánh bướm:
• Nửa đầu: X[k] = X_even[k] + T_k
• Nửa sau: X[k + N/2] = X_even[k] - T_k
• Trả về mảng kết quả 1D kiểu np.complex128.

Ràng buộc

• Thời gian chạy tối đa: 1000ms.
• Giới hạn bộ nhớ: 256MB.
• Dữ liệu đầu vào tuân thủ đúng kiểu dữ liệu và miền giá trị được mô tả.