为什么整数相乘是O(n^2)?

问题描述 投票:0回答:1

我想知道为什么整数乘法是O(n^2)?我被教导加法和乘法被视为 1 次运算。因此,如果我将一个 n 位整数与另一个 n 位整数相乘,我应该得到 O(n^2),这是正确的。但有人可以用例子向我解释一下吗?

示例

如果我想乘以 99 x 99。我只能数 3 次运算

  1. 99×9
  2. 99×90
  3. 891+8910 这只会给我 O(3),而它应该是 O(4)。
algorithm math big-o
1个回答
0
投票

乘法不是 O(n^2)。

整数与有界位数的乘法是 O(1),因为对有界大小输入的所有操作都是 O(1)。

无限大小整数的乘法需要 O(n log n) 时间,使用最知名的复杂度算法

某些简单的乘法算法

O(n^2),但它们仅适用于较小的整数。 这些算法的工作原理与用铅笔和纸相乘时使用的算法类似。 尝试使用您在学校学到的方法乘以 8194421 * 3882342。 您会发现您最终写下了大约 50 个数字。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.