不同渐近符号的乘法和加法

Question

有人知道如何进行这样的计算吗？

O(n^2) + THETA(n) + OMEGA(n^3) = ?

或者

O(n^2) * THETA(n) * OMEGA(n^3) = ?

通常情况下，如何添加和乘以不同的渐近符号？

- Sławosz

---

嗨，Sławosz。你的问题非常模糊。你能更具体地说明以下几点吗：1. 你感兴趣的结果是什么；2. 你的问题领域（渐近符号在一般代数和计算机科学中有不同的假设。我假设你指的是计算机科学，因为你没有在 math.SE 上发帖）；3. 你想要执行的方程类型（总是带着这些三个部分吗？原子数量有限还是无限的 O() 总和允许？等等...）；4. 确保我们谈论的是实数？5. 你感兴趣的结果是什么（O()？Omega()？）？ - Grzegorz Wierzowiecki

这里有一个例子，说明如何混淆O(n)+O(n)的概念。当我要求更多的标准时，我的意思是，留下常数O(n)+O(n)=O(n)可能会导致归纳步骤O(n)+O(n)+...=O(n)，这是错误的。因为(O(n))^n=O(n^n)，所以在这里需要非常具体地表述以避免混淆。 - Grzegorz Wierzowiecki

Answer 1

O表示一个上限；

Ω表示一个下限；

Θ表示一个渐进上界；

维基百科有一张好图来解释这些概念。

因此，它们通常不可比较。

对于第一个情况，

O(n^2) + Θ(n) + Ω(n^3)

让我们先解决 O。第一个术语告诉我们 O(n^2)，第二个术语告诉我们 O(n)。仅基于这两个，我们知道我们有一个上限为 O(n^2)。然而，第三个术语对于上限没有任何信息！因此，我们真的无法得出关于 O 的任何结论。

重点在于，O 和 Θ 只提供有关 O 的信息，Ω 和 Θ 只提供有关 Ω 的信息。这是因为 Θ(g(n)) 意味着 O(g(n)) 和 Ω(g(n))，所以我们可以根据给定的分析将 Θ 转换为适用于 O 或 Ω 中的任何一个。

然而，三者一起，甚至只有 O 和 Ω，都会让你感到茫然，因为 O 和 Ω 都不意味着关于另一个的任何信息。

- PengOne

Answer 2

您不能。假设您知道a > 0和b < 10。那么您对a+b没有任何信息。它可以是任何值。

对于函数，大O符号和大Ω符号的作用类似。

- tskuzzy

Answer 3

虽然我上面的答案对于一般函数和界限是正确的，但在计算机科学中，我们通常只考虑正函数。因此在你的第一个例子中，我们有：

O(n^2) + Theta(n) + Omega(n^3) = Omega(1)+Theta(n)+Omega(n^3) = Omega(n^3)

这源于函数都是正数的假设。也就是说，所有函数都是 Omega(1)。

- tskuzzy

---

同样地，问题中给出的乘法复杂度为Omega(n^4)。 - Aubrey da Cunha