Jauved

整数乘法为什么仍未找到理论极限

整数乘法为什么仍未找到理论极限 整数乘法看起来是最基础的运算之一, 但在算法理论中仍有一个没有解决的问题: 两个长度为 $n$ 的大整数, 最少需要多少计算量才能完成乘法? 目前已知的理论算法可以达到: [O(n\log n)] 但数学家尚未证明, 这已经是整数乘法能够达到的最快速度. 1. 什么是算法复杂度 算法复杂度描述的是: 当输入规模增大时, 算法的工作...