Hi 성현!



 sh0416:

…
What is the time complexity of fft function if we do not use GPU?
Is this function use divide-and-conquer algorithm for calculating fft?


I haven’t actually looked at the code, but the time complexity
should be n log n.
After all, the function in question is torch.fft, where “fft”
stands for “fast Fourier transform,” which uses what you call
the “divide-and-conquer” algorithm and runs in n log n.
It would be false advertising if torch.fft instead used the
sft* algorithm.
*) “Slow Fourier transform”
Best regards.
K. Frank