big-o - 为什么天真的乘法 n^2 时间？

Question

我读过诸如加法/减法之类的运算是线性时间，而“小学”长乘法是 n^2 时间。为什么这是真的？

floor(log n)当 n 是较小的操作数时，不是加法时间吗？同样的论点也适用于减法和乘法，如果我们编写一个程序来进行长乘法而不是将整数加在一起，那么复杂性不应该是floor(log a) * floor(log b)a 和 b 是操作数的地方吗？

score 7 · Accepted Answer

答案取决于什么是“n”。当他们说加法是 O(n) 并且乘法（使用朴素算法）是 O(n^2) 时，n 是数字的长度，以位或其他单位为单位。使用此定义是因为任意精度算术被实现为“数字”列表（不一定以 10 为基数）的操作。

如果 n 是要相加或相乘的数字，只要数字存储在 log n 空间中，复杂度将是 log n 和 (log n)^2（对于正 n）。

score 1 · Accepted Answer

（例如）乘法的天真的方法273 x 12被扩展为（使用分配规则）(200 + 70 + 3) x (10 + 2)或：

  200 x 10 + 200 x  2 
+  70 x 10 +  70 x  2
+   3 x 10 +   3 x  2

这种简化的想法是将乘法减少到可以轻松完成的事情。对于您的小学数学，假设您知道从零到九的乘法表，那将与数字一起使用。对于每个“数字”可能是 0 到 9999 之间的值（为了便于十进制打印）的 bignum 库，同样的规则适用，能够相对恒定地将小于 10,000 的数字相乘）。

因此，如果n是位数，那么复杂性确实是因为“恒定”操作的数量往往会随着“位数”计数的乘积而增加。O(n²)

即使您对 digit 的定义略有不同（例如从 0 到 9999 的值，甚至是二进制数字之一0或1）也是如此。

2 回答 2