标签FFT下的文章

fz 发布于 04月06, 2019

快速数论变换的时间复杂度问题

前不久,看到了个大新闻,有人提出了个的整数乘法算法。不过据说是理论意义大于实际意义。看到这个我就很奇怪了,使用FFT的整数乘法算法的时间复杂度之前难道不就是吗?然后我看到了知乎上相关的讨论,说以前的复杂度是。难道我一直都搞错了吗?经过一番研究后发现,这是由于我们对和运算的定义不同导致的。说复杂度为的,指的是二进制位的个数,其基本运算是二进制位的运算。而具体到我们的常见实现,我们通常采用十进制数下的...

阅读全文 »