其中 指对m比特的进行相乘的复杂度。

在计算机进行乘法计算的时候，传统的计算方法采用了类似竖式计算的方法——正如我们在小学课堂里面所学到的那样，因此时间复杂度是O(n ^ 2)。在进行大数（比如说数字位数超过2048）乘法计算的时候，目前的做法是Schönhage–Strassen算法，该算法利用快速傅里叶变换，将算法的复杂度降到O(n log n log log n)。

最近，Harvey 和Van Der Hoeven 在HAL贴出了两人合著的新论文“Integermultiplication in timeO(n log n)”，宣称已经发现时间复杂度为O(n log n)的整数乘法算法。
作者：留德华叫兽
链接：https://zhuanlan.zhihu.com/p/62143130
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

在通常意义下，为

在极限下，为

空间复杂度包含：

其中k是常数项，具体取决于算法。