关于二维卷积
  • 板块学术版
  • 楼主xtx1092515503
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/1/1 11:13
  • 上次更新2023/10/28 13:12:44
查看原帖
关于二维卷积
123369
xtx1092515503楼主2022/1/1 11:13

二维卷积的暴力做法是 O(n2m2)O(n^2m^2) 的。虽然有 nm(logn+logm)nm(\log n+\log m) 的二维 FFT 法,但是在 n,mn,m 小且模数不是 NTT 模数时不实用。秦九韶+拉格朗日插值可以做到 nm(n+m)nm(n+m),但是常数太大。请问有没有简单一点的 nm(n+m)nm(n+m) 算法?非常感谢!

2022/1/1 11:13
加载中...