前不久，看到了个大新闻，有人提出了个的整数乘法算法。不过据说是理论意义大于实际意义。

看到这个我就很奇怪了，使用FFT的整数乘法算法的时间复杂度之前难道不就是吗？然后我看到了知乎上相关的讨论，说以前的复杂度是。难道我一直都搞错了吗？

经过一番研究后发现，这是由于我们对和运算的定义不同导致的。说复杂度为的，指的是二进制位的个数，其基本运算是二进制位的运算。而具体到我们的常见实现，我们通常采用十进制数下的万进制来实现，也就是个int或者long long，以及在其上的整数运算，我们认为它是的。因此，如果把运算粒度缩小到二进制位的运算上，必须衡量该的运算量。因此，是先对进行一次，相当于切换到十进制或者万进制的表示过程；而再进行一次，相当于对每个十进制或者万进制数的乘法（这一乘法是取决于数的位数的，也就是该数的）。

PS: 此处讨论的是基于快速傅里叶变换（FFT）的快速数论变换（NTT）。