众所周知,长度为 nnn 的 FFT 的时间是 O(nlogn)O(n\log n)O(nlogn) 的。
但尽管 Schönhage–Strassen 大数乘法使用的是 FFT(更准确地是 NTT),为什么它的复杂度是 O(nlognloglogn)O(n\log n\log\log n)O(nlognloglogn)?