rt，大部分地方称其复杂度为 $O(n\log n)$，主定理分析结果也是这样，但《算法导论》和这篇文章第 $274$ 页称其复杂度为 $O(n\log n\log\log n)$，那么它的复杂度究竟如何呢？

注：《算法导论》里 FFT 那一章说的是 $O(n\log n)$，而是后面数论算法开头提到目前已知最快的方法需要 $O(n\log n\log\log n)$ 的时间。