algorithm - 相乘和相加不同的渐近符号

Question

有谁知道如何进行这样的计算示例:

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

或

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

一般情况下，不同的渐近符号如何相加和相乘？

Answer 1

O 给出了一个上限；

Ω 给出了一个下限；

Θ 给出一个渐近边界；

Wikipedia有一个很好的图表来解释这些。

因此这些在一般情况下确实没有可比性。

对于你的第一个案例，

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 也不是 Ω 暗示关于另一个的任何事情。