乘法和加入不同asymptotioc符號

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也不Ω暗示有關的任何其他。

Answer 2

你不能。假設你知道a > 0和b < 10。那麼你沒有關於a+b的信息。它可能是任何東西。

Big-O和Big-Omega的功能相似。

Answer 3

雖然我的上述答案對於一般函數和邊界是正確的，但在計算機科學中，我們通常只考慮正函數。因此，在您的第一個示例中，我們有：

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

這源於功能都爲正的假設。也就是說，所有功能都是Omega(1)。