algorithm - 基本算术运算的大 O 复杂度

Question

基本算术运算（如乘法、平方根、对数、标量和矩阵乘积）的广泛算法的 Big-O 复杂度是多少？

就大 O 复杂性而言，是否有更有效的奇异算法，但在实际解决方案中不是很普遍（例如，没有在流行的软件库中实现）？

score 18 · Accepted Answer

方阵的矩阵乘积：

还有一个 O(N ^2.38 ) Coppersmith–Winograd 算法，但由于隐藏常数巨大，我认为它并不广泛。

大整数乘法：

还有一个 n log n · 2 ^{O(log* n)}算法于 2008 年发布，但它太新而无法普及。

通常，naïve 方法对于正常大小的输入来说已经足够好了。

score 6 · Accepted Answer

您会将最简单的操作视为 O(1)，因为您的输入大小通常是固定的（即 32 位或 64 位）。

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

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

只是不要使用Schönhage–Strassen来乘以“正常”小数。它会让我哭泣。仅仅因为算法是 O( n ² ) 并不意味着它很糟糕——尤其是当n几乎总是 2 ⁵或 2 ⁶时。

score 5 · Accepted Answer

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

score 1 · Accepted Answer

看看BigInteger，关于任意长度的整数。就输入的大小而言，现在一切都有成本，即位数（通常是数字的位数O(log K)）K。我将N用于下面的位数。

比如现在的加减法O( N )。乘法要么是O( N^2 )（天真的），要么O( n (log n)^(2+epsilon) )是 FFT。

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

BigDecimals 有额外的复杂性，它是任意长度的十进制等价物，除了一些更基本的操作之外，一些事情也更有趣（特别是如果你想弄清楚你想要多少精度）。你可以看看Java的实现。

score 1 · Accepted Answer

平方根和对数可以以多种方式实现，极大地影响复杂性（根据所需的精度来判断）。

如果它们是用查找表（和某种插值）实现的，内存需求确实会随着需要更高的精度而爆炸，但复杂性在于在数组中查找值并可能应用插值。

更普遍的是，它们似乎是通过它们的系列定义来实现的。递归或迭代语句数轮，直到达到所需的精度。在这里，由于需要更高的精度，轮数可能会变得非常高，并且计算本身也会受到精度提高的影响。

score 0 · Accepted Answer

大量比特的除法和平方根并不比乘法复杂多少。对于这两种操作，普通的旧牛顿迭代可以安排成牛顿迭代只有乘法。由于每一步正确数字的数量加倍，因此我们可以将每一步的计算精度加倍。

score 0 · Accepted Answer

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

我认为有一个版本的 Strassen 算法在整数乘法方面比正常的稍微好一点，但现在我想起来了，它最终还是一样简单......

加法和减法差不多，只是加法和减法。除法和平方根可能很有趣......

还：请注意，到目前为止，每个人都在谈论 INTEGER 算术。一旦你进入浮动/双打，所有的赌注都关闭了。然后你进入数值分析的世界，那是它自己的整个领域......

7 回答 7