求助高精度乘法
  • 板块学术版
  • 楼主zhangbo1000
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/2/28 13:30
  • 上次更新2024/2/28 17:20:23
查看原帖
求助高精度乘法
760291
zhangbo1000楼主2024/2/28 13:30

在进行高精度乘法时,理论上 Karatsuba 算法时间复杂度为 O(nlog⁡23)>O(nn)O(n^{\log_23})>O(n\sqrt{n}),远高于 FFT 的 O(nlog⁡n)O(n\log n),P1919 的评测结果(FFT 约 5s,Karatsuba(压 88 位) 约 13s)也证明了这一点,但一些书和题解评论区的一些人说压位 Karatsuba 速度快于 FFT,这是什么原因?

2024/2/28 13:30
加载中...