Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Toán cho CNTT] So sánh số phép nhân: DFT vs FFT

    DFT vs FFT — đếm phép nhân phức

    DFT trực tiếp cần n2n^2n2 phép nhân phức. FFT cơ số 2 chỉ cần n2log⁡2n\frac{n}{2}\log_2 n2n​log2​n phép nhân twiddle (số butterfly).

    Cho nnn (lũy thừa của 2), in hai số: chi phí DFT và chi phí FFT.

    Ví dụ

    Với n=8n = 8n=8: DFT =64= 64=64, FFT =4⋅3=12= 4\cdot 3 = 12=4⋅3=12.

    • Định dạng đầu vào:

      Một số nguyên nnn (lũy thừa của 2).

    • Ràng buộc đầu vào:

      n∈{1,2,4,…,1024}n \in \{1,2,4,\dots,1024\}n∈{1,2,4,…,1024}.

    • Định dạng đầu ra:

      Một dòng gồm hai số nguyên: số phép nhân của DFT và của FFT, cách nhau dấu cách.

    Ví dụ:

    Đầu vào:

    8

    Đầu ra:

    64 12

    Giải thích:

    DFT=8^2=64; FFT=(8/2)*log2(8)=4*3=12.

    Đang tải editor...