Toán học & Đa thức
Number Theoretic Transform (NTT)
ID: #142
Xem trên trang chủ
Thời gian (Time)
O(N log N)
Không gian (Space)
O(N)
Mô tả nguyên lý
Thuật toán FFT trên trường hữu hạn modulo nguyên tố, tránh sai số số thực.
Cài đặt mẫu (Implementation)
// Sử dụng căn nguyên thủy bậc n thay thế cho số phức trong biến đổi Fourier nhanh.