漸進記号
Θ(theta)：漸進緊确界。f(n) = Θ(g(n))表示：∃c1>0,c2>0,n0>0,s.t.對∀ n>n0,0 ≤c1g(n) ≤ f(n) ≤ c2g(n)成立。用極限表示為limn->∞f(n)/g(n) = c.
O(大歐):漸進上界。 f(n) = O(g(n))表示 ：∃c>0,n0>0,s.t.對∀ n>n0,0≤ f(n) ≤ cg(n)成立。
Ω(大omega):漸進下界。f(n) = Ω(g(n))表示 ：∃c>0,n0>0,s.t.對∀ n>n0,0≤ cg(n)≤ f(n) 成立。
o(小歐):非漸進緊确上界。 f(n) = o(g(n))表示 ：對∀c>0,∃n0>0,s.t.對∀ n>n0,0≤ f(n) <cg(n)成立。 f(n) = o(g(n))與 f(n) = O(g(n))的主要差別在于：前者是對任意c>0，0≤ f(n) ≤ cg(n)成立，而後者是對某個c>0,0≤ f(n) <cg(n)成立。也就是說，f(n) = o(g(n))可以表示為，當n->∞時，limf(n)/g(n) = 0.
ω(小omega)：非漸進緊确下界。 f(n) = ω(g(n))表示 ：對∀c>0,∃n0>0,s.t.對∀ n>n0,0≤ cg(n)<f(n)成立。可用極限表示為：當n->∞時，limf(n)/g(n) = ∞.
我們記 f(n) = O(g(n))以指出函數 f(n) 是集合 O(g(n))的成員，即f(n)∈ O(g(n))。注意，f(n) = Θ(g(n))蘊含着f(n) = O(g(n))，也就是說，O(g(n))⊆ Θ(g(n))。同樣地，Ω(g(n))⊆ Θ(g(n))。由此可得如下重要定理：
對于任意兩個函數f(n)和g(n)，我們有f(n) = Θ(g(n)),當且僅當f(n) = O(g(n))且f(n) = Ω(g(n))。
漸進記号的性質
傳遞性：
f(n) = Θ(g(n))且g(n) = Θ(h(n)),則 f(n) = Θ(h(n))
f(n) = O(g(n))且g(n) = O(h(n)),則 f(n) = O(h(n))
f(n) = Ω(g(n))且g(n) = Ω(h(n)),則 f(n) = Ω(h(n))
f(n) = o(g(n))且g(n) = o(h(n)),則 f(n) = o(h(n))
f(n) = ω(g(n))且g(n) = ω(h(n)),則 f(n) = ω(h(n))
自反性：
f(n) = Θ(f(n))
f(n) = O(f(n))
f(n) = Ω(f(n))
對稱性：
f(n) = Θ(g(n))當且僅當g(n) = Θ(f(n))
轉置性:
f(n) = O(g(n))當且僅當g(n) = Ω(f(n))
f(n) = o(g(n))當且僅當g(n) = ω(f(n))
因為這些性質對漸進記号成立，是以，可以将兩個函數f和g的漸進比較與實數a與b之間的比較做一種類比：
f(n) = Θ(g(n))類似于a = b
f(n) = O(g(n))類似于a ≤ b
f(n) = Ω(g(n))類似于a ≥b
f(n) = o(g(n))類似于a <b
f(n) = ω(g(n))類似于a >b
然而，實數的下列性質不能攜帶到漸進記号：
三分性：對于任意兩個實數a和b，下列三種情況恰有一種必須成立：a<b,a>b或a=b。
雖然兩個實數可以互相比較，但是不是所有的函數都可以漸進比較。也就是說，對于兩個函數f(n)和g(n) 也許f(n) = O(g(n))和f(n) = Ω(g(n))都不成立。例如，我們無法使用漸進記号比較n和n1+sin n
轉載于:https://www.cnblogs.com/begodlike/p/5986518.html