数据结构与算法分析C++语言描述 Algorithm Alnalysis

渐近表示法

渐近上界

\( T(N) = O(f(N)) \) if there are positive constants \( c \) and \( n_0 \) such that \( T(N) \leq cf(N) \) when \( N \geq n_0 \) 。

渐近下界

\( T(N)= \Omega (g(N)) \) if there are positive constants \( c \) and \( n_0 \) such that \( T(N) \geq cg(N) \) when \( N \geq n_0 \)。

渐近紧确界

\(T(N)=\Theta (h(N)) \) if and only if \( T(N) = O(h(N)) \) and \( T(N) = \Omega (h(N)) \)。

非渐近紧确上界

\(T(N)=o(p(N)) \) if \( T(N) = O(p(N)) \) and \( T(N) \neq \Theta (p(N)) \)。