mxqz 关于 FFT 的复杂度
  • 板块灌水区
  • 楼主esquigybcu
  • 当前回复5
  • 已保存回复5
  • 发布时间2022/3/8 21:16
  • 上次更新2023/10/28 07:00:46
查看原帖
mxqz 关于 FFT 的复杂度
384214
esquigybcu楼主2022/3/8 21:16

众所周知,长度为 nn 的 FFT 的时间是 O(nlogn)O(n\log n) 的。

但尽管 Schönhage–Strassen 大数乘法使用的是 FFT(更准确地是 NTT),为什么它的复杂度是 O(nlognloglogn)O(n\log n\log\log n)

2022/3/8 21:16
加载中...