基本算术操作的时间复杂度

Question

基本算术操作（如乘法，平方根，对数，标量和矩阵乘积）常见算法的大 O 复杂度是多少？

是否有一些异类算法，它们在大 O 复杂度方面更加高效，但在实际解决方案中并不常见（例如不在流行的软件库中实现）？

- psihodelia

---

+1 有趣的问题。为了澄清，他可能是指随着位数增加而增加的复杂度。 - Tronic

@Tronic：你认为位元吗？矩阵乘积可能是基于矩阵大小的推测... - Skilldrick

我认为这不是社区维基，而是一个真正的技术问题... - Brian Postow

@Brian：这更像是一道调查问题，适合于社区维基（CW）。我预计你会看到很多答案，对未来的提问者可能不容易理解。 - Aryabhatta

@Moron，这不是一个调查问题，因为它在询问意见。它是一个调查问题，因为它非常广泛，可能会得到很多不同的答案，就像你所说的...如果这就是你的意思，那么是的。我通常认为CW适用于意见或有趣类型的问题，我们不需要担心给人们回答的声誉...（或者剥夺）。 - Brian Postow

@Brian。是的，我的意思是它非常广泛。我将社区Wiki视为维基百科：一种信息性的文章/页面/帖子，覆盖某个主题的广度（也许还有些深度）。你是否有可用的声望应该是无关紧要的。将其标记为CW将允许人们编辑其他人的答案以消除冗余/ consololidate答案等。 - Aryabhatta

Answer 1

请参见 http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations

---

方阵矩阵乘积：

• （朴素算法）O(N³)
• (Strassen算法) O(N^2.81)

还有一个O(N^2.38)的Coppersmith–Winograd算法，但由于巨大的隐藏常数，它并不普及。

大整数乘法：

• （朴素算法）O(n²)
• (Schönhage–Strassen算法) O(n log n log log n) 基于快速傅里叶变换。

2008年也发表了一种O(n log n · 2^{O(log* n)})的算法，但这种算法太新，普及率不高。

---

通常情况下，朴素算法对于常规大小的输入已足够。

- kennytm

---

有趣的是，O(N^2.38) 比 O(N³) 更快。 - psihodelia

很遗憾，对于这个问题的答案是“取决于情况”。正如维基百科文章提到的那样，该算法并不广泛使用，因为它只会在实际上输入非常大的情况下才能减少运行时间。 - Iain Galloway

实际上，O(N^2.38)算法并不比其他算法更快，因为速度不仅取决于算法复杂度。 - Pillsy

“快速”乘法方法也是同样的道理。当n为2的8次方时，O(n平方)并不算太大。Schönhage-Strassen方法在处理非常庞大的数字时才值得考虑（维基百科建议在开始获得回报前至少需要2^15 - 2^17个数字）。 - Iain Galloway

@KennyTM：什么是“大整数”？ - Lazer

@eSKay：任意精度整数。 - kennytm

Answer 2

你会认为大多数简单操作都是O(1)，因为你的输入大小通常是固定的（即32位或64位）。

在正常情况下，您的平台将执行完全相同的乘法、平方根、对数等操作，而不考虑您的输入的“大小”（即int a = 0;和int b = Int32.MaxValue都是32位整数）。

一旦您开始查看矩阵或表示任意精度数字，就会变得有趣，但是有人已经链接了维基百科摘要，所以我不会详述。

只是不要使用Schönhage–Strassen来乘以“普通”小数字。它会让我哭泣。仅因为一个算法是O(n^2)并不意味着它很差--特别是当n几乎总是2^5或2^6时。

- Iain Galloway

---

实际上，你对于简单操作是正确的。然而，作为一个理论家，我想说，你仍然可以从数字位数的角度来讨论复杂性。同样的算法可能适用于32位，但对于64位或者最终达到1024位等情况会变得缓慢...再次强调，现实中你是正确的，但这仍然是一个有趣的问题。 - Brian Postow

“点头”，一旦您走出固定长度输入的安全世界，这绝对是一个有趣的问题。 - Iain Galloway

Answer 3

操作本身并没有复杂度，算法才有。例如，有各种不同的平方根算法，它们的复杂度也会不同。

- Skilldrick

---

乘法是两个位数组之间的算法。如果我没记错的话，它的复杂度为O(n²)。 - Tronic

@Skilldrick：OP正在谈论最常用的算法，所以从某种意义上说，这个答案是无关紧要的。 - Aryabhatta

使用FFT乘法仅需O(n logn)的时间复杂度。 - Ritsaert Hornstra

FFT乘法不仅是“O(n log n)”。好吧，也许如果n是数字的话，但在这些术语中，n通常是位数。 - Larry

@Skilldrick：我看到你还没有“自律徽章”;-) - Aryabhatta

Answer 4

平方根和对数可以用多种方式实现，这会极大地影响复杂度（通过所需精度来判断）。

如果它们使用查找表（和某种插值方法）实现，随着需要更高的精度，内存需求会急剧增加，但复杂度只是在数组中查找值并可能应用插值。

更流行的做法似乎是通过它们的级数定义来实现。递归或迭代一个语句一定次数，直到达到所需精度。在这里，所需次数可能会非常高，因为需要更高的精度，而且计算本身也会受到增加精度的影响。

- Tronic

---

@skilldrick，你绝对可以用那种方式做。有些算法是根据它们的输出大小而不是输入大小来衡量的。它们有一个名字，但今天是星期五，所以我懒得记住它 B-) - Brian Postow

Answer 5

看一下BigInteger，它是关于任意长度整数的。现在每个操作都有一个成本，以输入大小为代价，即位数（通常对于数字K，位数为O(log K)）。以下我将使用N表示位数。

例如，加法和减法现在是O(N)。乘法可以是朴素的O(N^2)，也可以是O(n (log n)^(2+epsilon))，其中使用FFT算法。

其他算法包括“幂”函数，需要O(N)次乘法。（但现在每个乘法都有一个成本！）

对于BigDecimals，即任意长度的十进制数，还有其他复杂性，除了一些基本操作外，一些更有趣的事情也很重要（特别是如果您想弄清楚需要多少精度）。您可以查看Java的实现。

- Larry

---

幂函数的朴素实现需要O(n)次乘法，但是聪明的实现只需要O(log n)次：http://en.wikipedia.org/wiki/Exponentiation_by_squaring - Juliet

正如我之前提到的，N 是位数。然而，幂运算对于某些数字 K 确实是 O(log K) 的。 - Larry

Answer 6

大量位数的除法和平方根计算并不比乘法更复杂。对于这两种操作，普通的牛顿迭代可以被安排成只包含乘法。由于每一步中正确数字的数量增加了一倍，我们可以在每一步中将计算精度加倍。

- gnasher729

Answer 7

有一种傅里叶类型的算法也可以进行整数乘法（Schonhage-Strassen）

我曾认为 Strassen 算法有一个版本可以稍微比普通整数乘法更好，但现在想想，那个版本最终与直接方法相同...

加法和减法基本上就是加法和减法。除法和平方根可能会有趣一些...

此外：请注意，到目前为止，每个人都谈论了整数算术。一旦涉及浮点数/双精度浮点数，一切都不确定了。然后你就进入了numerical analysis 的世界，那是一个完全不同的领域...

- Brian Postow