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

Question

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

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

Answer 1

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

---

平方的矩阵乘积矩阵：

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

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

大整型乘法：

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

还有一个 n log n · 2^{O(log* n)} 算法于 2008 年发布，但由于太新而无法广泛传播。

---

通常，朴素方法对于正常大小的输入来说已经足够了。

Answer 2

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

在正常情况下，您的平台将执行完全相同的乘法、平方根、对数等操作，无论您的输入“大小”如何（即 int a = 0；和 int b = Int32.MaxValue 均为 32 位）整数）。

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

只是不要使用 Schönhage–Strassen 来乘以“正常”小数字。它会让我哭泣。仅仅因为算法的时间复杂度为 O(n²) 并不意味着它不好 - 特别是当 n 几乎总是 2^{5< /sup> 或 26。}

Answer 3

运算不复杂，算法复杂。例如，平方根算法有多种，它们的复杂度也不同。

Answer 4

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

如果它们是用查找表（和某种插值）来实现的，那么内存需求确实会激增，因为需要更高的精度，但复杂性在于查找数组中的值并可能应用插值。

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

Answer 5

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

例如，加法和减法现在是O( N )。乘法是 O( N^2 ) （简单）或使用 FFT 的 O( n (log n)^(2+epsilon) )。

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

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

Answer 6

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

我认为 Strassen 算法的一个版本在整数乘法方面比正常算法稍好一些，但现在我想到了，最终结果与简单的相同......

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

另外：请注意，到目前为止每个人都谈论过整数算术。一旦你达到了浮动/双打，所有的赌注就都结束了。然后你就进入了数值分析的世界，这是它自己的一个完整领域。 。

Answer 7

大量位数的除法和平方根并不比乘法复杂多少。对于这两种运算，普通的旧牛顿迭代可以以牛顿迭代仅具有乘法的方式进行排列。由于每一步的正确位数都会加倍，因此我们只需将每一步的计算精度加倍即可。