O notation:
O(g(n))={f(n): there exists consts c>0 no>0 such taht 0<=f(n)<=c*g(n) for all n>no}
f(n)=O(g(n)) represents an anonymous function[f(n)] in that set[O(g(n))].
Ex1. f(n)=n^3+O(n^2) means there is a function h(n) in O(n^2) such that f(n)=n^3+h(n);
Ex2. n^2+O(n)=O(n^2) the '=' means is and it is not symmetric.
Summary: the O notation represents the upper bounds.
--------------------------------------------------------------------------------------------------------
Ω notation:
Ω(g(n))={f(n): there exists consts c>0 no>0 such taht 0<=c*g(n)<=f(n) for all n>no}
Summary: the Ω notation represents the lower bounds.
--------------------------------------------------------------------------------------------------------
Θ notation:
Θ(g(n))={f(n): there exists consts c1>0 c2>0 no>0 such taht 0<=c1*g(n)<=f(n)<=c2*g(n) for all n>no}
Summary: Θ(g(n))=O(g(n))∩Ω(g(n)).
--------------------------------------------------------------------------------------------------------
o & ω:
o(g(n))={f(n): for any positive consts c>0 there exists a constant no>0 such taht 0<=f(n)<c*g(n) for all n>no}
ω(g(n))={f(n): for any positive consts c>0 there exists a constant no>0 such taht 0<=c*g(n)<f(n) for all n>no}
--------------------------------------------------------------------------------------------------------
O: <=
Ω: >=
Θ: ==
o: <
ω: >
因篇幅问题不能全部显示，请点此查看更多更全内容