我想知道为什么整数乘法是O(n^2)?我被教导加法和乘法被视为 1 次运算。因此,如果我将一个 n 位整数与另一个 n 位整数相乘,我应该得到 O(n^2),这是正确的。但有人可以用例子向我解释一下吗?
如果我想乘以 99 x 99。我只能数 3 次运算
乘法不是 O(n^2)。
整数与有界位数的乘法是 O(1),因为对有界大小输入的所有操作都是 O(1)。
无限大小整数的乘法需要 O(n log n) 时间,使用最知名的复杂度算法。
某些简单的乘法算法是 O(n^2),但它们仅适用于较小的整数。 这些算法的工作原理与用铅笔和纸相乘时使用的算法类似。 尝试使用您在学校学到的方法乘以 8194421 * 3882342。 您会发现您最终写下了大约 50 个数字。