嗨,我正在学习Big-O,并想知道为什么乘法是O(n ^ 2).我想我知道为什么,但我不确定.是因为乘法工作需要多长时间？我知道加法是线性时间O(n),如果我们进行二进制乘法,我们首先将所有位相乘并移位.在我们完成移位并将所有位相乘后,我们将进行加法.所以我猜测乘法的递归调用是O(n),结果的加法是O(n).因此梳理两个运行时间将给我们O(n ^ 2).这是对的还是我走错了路？编辑:所以我猜我要问的是为什么小学派的乘数是O(n ^ 2)
谢谢
Chr*_*eck 11
首先,乘以什么？你是乘法,矩阵？你是乘法,多项式？你是乘法,整数？你是乘以浮点数吗？你是乘法,整数模数？
假设你正在谈论在小学阶段学到的整数乘法 -
该(幼稚)小学的算法是O(n^2)因为当你乘一个n由数位数字m用它位数,你最终得到的基本上是一个总和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).