2016-09-24 43 views
0

我想了解這些方程式。我必須確定哪些是錯誤的,但我真的很想了解如何做到這一點。漸近表示法理解

1. $\theta(n)+O(n)=\omega(n)$ 
2. $O(n)+\sigma(n)=\theta(n)$ 
3. $\theta(n)+O(n)=O(n)$ 
4. $f(n)=O(n)$ implies $g(n)=\omega(f(n))$ 

我知道你要讀

$$ \ THETA(N)+ O(N)= \歐米茄(n)的$$ 如下:如果我的主要我有2種方法

main(){ 
m1(); 
m2(); 
} 

和方法M1的運行時間是\ tetha(n)和M2的運行時間爲O(n), 我可以說,主的運行時間是\歐米茄(N)?

我認爲第三個是錯誤的。那是正確的嗎?

回答

0

你是對的,因爲即使m2小於O(n)m1的漸近運行時間仍然有較低的界限,因爲界限很緊。

編輯:#1是背後的原因