你好，我正在学习大O表示法，想知道为什么乘法的时间复杂度是O(n^2)。我觉得我知道原因，但不确定。乘法的时间复杂度高是因为它需要花费更长的时间吗？我知道加法是线性时间O(n)，如果我们进行二进制乘法，首先要将所有位数相乘并移位。当我们完成了所有位数的移位和相乘后，就会进行加法。所以我猜乘法的递归调用是O(n)，结果的加法也是O(n)。所以两个运行时间的结合将给出O(n^2)。这样对吗，还是我走错了路？ 编辑： 那么我猜我的问题是为什么小学的乘法是O(n^2)。
谢谢
1个回答
11
首先，你要乘以什么？你是在乘矩阵吗？你是在乘多项式吗？你是在乘整数吗？你是在乘浮点数吗？你是在对模质数的整数取模后相乘吗？
假设你说的是我们在小学学过的整数乘法--
（朴素的）小学算法时间复杂度为O(n^2)，因为当你用它将一个n位数乘以一个m位数时，你最终得到的是一个n位数的大概m个移位副本，你需要将它们全部加起来。这涉及写下大约n+m行、 m列的数字网格，然后将所有这些数字加起来，所以在该方法中总共需要约n^2的时间和空间。
然而，现在已经发明了许多更好的乘法方法，如俄罗斯农民乘法，对于极大的数字，最快的方法可以达到大约O(n log n)的时间复杂度。这些方法基于快速傅里叶变换，并且非常复杂。
没有人知道如何证明乘法不能在O(n)的时间内完成，理论上可能是可以的。
所以，当你问“为什么乘法的时间复杂度是O(n^2)”时，答案是不是这样的，确切的时间复杂度在O(n)和O(n log n)之间，只有某些算法的时间复杂度是O(n^2)。
假设你说的是我们在小学学过的整数乘法--
（朴素的）小学算法时间复杂度为O(n^2)，因为当你用它将一个n位数乘以一个m位数时，你最终得到的是一个n位数的大概m个移位副本，你需要将它们全部加起来。这涉及写下大约n+m行、 m列的数字网格，然后将所有这些数字加起来，所以在该方法中总共需要约n^2的时间和空间。
然而，现在已经发明了许多更好的乘法方法，如俄罗斯农民乘法，对于极大的数字，最快的方法可以达到大约O(n log n)的时间复杂度。这些方法基于快速傅里叶变换，并且非常复杂。
没有人知道如何证明乘法不能在O(n)的时间内完成，理论上可能是可以的。
所以，当你问“为什么乘法的时间复杂度是O(n^2)”时，答案是不是这样的，确切的时间复杂度在O(n)和O(n log n)之间，只有某些算法的时间复杂度是O(n^2)。
- Chris Beck
11
点赞不仅因为这是正确的答案，而且因为你在9分钟内写出了它。那一定是某种记录。但我认为如果答案中有更多关于这个主题的材料链接，那么它会更好。 - Juan Lopes
抱歉，我忘记说明我正在计算m位数x和n位数y的乘积。如果是这种情况，我的第一思路是否正确，因为我在考虑长乘法？ - Ronnie Garcia
@RonnieGarcia: 当你说到这一部分“我知道加法是线性时间O(n)，如果我们进行二进制乘法，首先要将所有位相乘并移位。完成移位和所有位相乘后，再进行加法。”听起来像是俄罗斯农民乘法。但当你说到“所以我猜递归调用乘法的时间复杂度是O(n)，而结果的加法则是O(n)。”我不确定递归调用是什么。所以最好写出实际的伪代码。 - Chris Beck
@Juan Lopes：“那一定是某种记录”。嘿嘿，这只是一天的工作而已 :) 所以我不确定要添加哪些链接，我的意思是我可以添加到维基百科或其他地方，但感觉有点毫无意义。如果您想要这些算法的参考资料，最好是参考一些教科书或一些论文，我猜这需要很多工作。我认为OP可能只关心小学算法之类的东西，但也不确定。 - Chris Beck
1@RBarryYoung：在某些情况下，卷积确实用于多项式的乘法。我在帖子中提到的算法，对于整数来说，是Schonage-Strassen算法，它更像是一系列的卷积而不是单个卷积，如果我理解正确的话。 - Chris Beck
显示剩余6条评论
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接