嗨，我正在学习Big-O，并想知道为什么乘法是O（n^2）。我想我知道为什么，但我不确定。这是因为乘法有多长时间？我知道加法是线性时间O（n），如果我们做二进制乘法，我们首先将所有的位相乘并移位它。在我们完成移位并乘以所有位后，我们将会进行加法。所以我猜测乘法的递归调用是O（n），结果的加法是O（n）。所以梳理两个运行时间会给我们O（n^2）。这是对的还是我在错误的轨道上？ 编辑： 所以我想什么，我问的是，为什么是小学乘法是O（n^2）为什么乘法O（n^2）？
感谢
所有的首先，乘以什么？矩阵乘法吗？你乘以多项式吗？整数倍吗？你是乘法浮点数吗？您是否乘以整数模数？
假设你正在谈论整数的乘法，你在小学学 -
因为当你用m位数相乘的n位数字号码使用它的（幼稚）小学的算法是O(n^2)，你最终会得到m移位副本的n数字，然后你必须加起来。它包括写下大约n+m,m数位网格，然后将所有这些数字相加，因此您需要大约n^2时间和空间。
但是，有许多更好的乘法方法已知，如俄罗斯农民乘法，并且对于非常大的数字，最快的方法实现大致O(n log n)时间。这些方法基于快速傅里叶变换，并且非常复杂。
没有人知道如何证明乘法不能在O(n)时间完成，理论上可能是这样。
所以，当你问
为什么乘法为O（n^2）？
答案是，它不是，它究竟是什么，我们不知道，它的位置在O(n)和O(n log n)之间。只有某些算法是O(n^2)。
Upvoting不仅仅是因为这是正确的答案，还因为你在9分钟内写完了。这一定是某种记录。但是我认为，如果它有更多关于该主题的材料的链接，答案会更好。 –
对不起，我忘了把m位数x和n位数y相乘。如果是这样的话，那么当我考虑长乘法时，我的第一条思路是否正确呢？ –
@RonnieGarcia：所以当你说这部分时“我知道加法是线性时间O（n），如果我们进行二进制乘法，我们首先将所有的位相乘并移位它，当我们完成移位并乘以所有位后做加法。“这听起来像俄罗斯农民增殖。但是当你这样说“所以我猜测乘法的递归调用是O（n），结果的加法是O（n）。”我不确定递归调用是什么。所以写实际的伪代码可能会更好？ –