algorithm - Karatsuba 算法对比 "*"运营商？

Question

今天，我听说了 Karatsuba 算法，一种快速乘法算法。我很好奇这个“快”是什么意思？

通常，我们在计算一段代码的时间复杂度时，会考虑使用 * 运算符作为 O(1) 的乘法运算，如果它始终为真，那么我们如何在渐近符号方面有更快的算法？或者当对非常大的数字执行时，不应将 * 视为 O(1)，而 Karatsuba 算法可能有用吗？

而在机器级别，编译器总是对 *.例如，使用按位运算将数字乘以 2^n。 Karatsuba 算法在实际运行时间上是否击败 *？

Answer 1

经典乘法是 O(n²)，其中 n 是被乘数的位数。

当测量普通计算机代码时，您处理的是固定大小(通常是 32 位或 64 位)的数字，因此它变为 O(1)(因为大小不会改变)

一旦开始处理 BigIntegers，这就变得非常重要。