渐进记号总结 & 《算法导论》 3.1

用来描述算法渐进运行时间的记号根据定义域为自然数集 \(\mathbb{N}\) 的函数来定义。

这样的记号对描述最坏情况运行时间的函数 \(T(n)\) 是方便的。

紧渐进界记号 \(\Theta\)

~~断句：紧渐进界记号~~

upd. 还是叫紧确渐进界记号 \(\Theta\) 比较好.. \[ \Theta(g(n)) = \{f(n) \mid \texttt{存在正常量} \,c_1,c_2\,\texttt{和}\,n_0\,\texttt{使得对所有}\,n\ge n_0\,\texttt{有}\,c_1g(n) \le f(n) \le c_2g(n)\} \] 例子 \(f(n) = 3n^2-n+5 = \Theta(n^2)\)

定理1：对于任意两个函数 \(f(n)\) 和 \(g(n)\) ，我们有 \(f(n)=\Theta(g(n))\) ，当且仅当 \(f(n)=O(g(n)) \land f(n) = \Omega(g(n))\)

或者等价的表示为： \(\Theta(f(n)) = O(n) \cap \Omega(n)\)

证明：显然。\(O,\Omega\) 记号的定义详见下文。

渐进上界记号 \(O\)

一般也写做 \(\mathcal{O}\) 。 \[ O(g(n)) = \{f(n)\mid\texttt{存在正常量}\, c \,\texttt{和} \,n_0 \,\texttt{使得对所有} \, n \ge n_0 \,\texttt{有}\,0\le f(n) \le cg(n)\} \]

例子：\(f(n) = 2n^2 + 3n + 1 =O(n^2),~f(n) = 2n = O(n^2)\) 。

渐进下界记号 \(\Omega\)

\[ \Omega(g(n)) = \{f(n)\mid\texttt{存在正常量}\, c \,\texttt{和} \,n_0 \,\texttt{使得对所有} \, n \ge n_0 \,\texttt{有}\,0 \le cg(n)\le f(n)\} \]

例子：\(f(n) = 2n+3 = \Omega(n),~f(n) = n^3 + 1 = \Omega(n)\) 。

非渐进紧确上界记号 \(o\)

断句：非渐进紧确上界记号

也叫非紧上界记号 \(o\) 。

注意区分大小写。 \[ o(g(n)) =\{f(n) \mid \texttt{对任意正常量} \,c\,,\texttt{存在正常量} \,n_0\,\texttt{使得对所有}\,n\ge n_0 \,\texttt{有}\, 0 \le f(n) < cg(n)\} \] 这等价于 \[ \lim\limits_{n \to +\infty} \dfrac{f(n)}{g(n)} = 0 \]

例子： \(f(n) = n \log_2 n = o(n^2)\)

但是 \(f(n) = n^2 -n \ne o(n^2)\) 。因为 \(n^2 - n = O(n^2)\) 是渐进紧确的。

非渐进紧确下界记号 \(\omega\)

断句：非渐进紧确下界记号

也叫非紧下界记号 \(\omega\) 。

注意这是 omega ，不是 w \[ \omega(g(n)) =\{f(n) \mid \texttt{对任意正常量} \,c\,,\texttt{存在正常量} \,n_0\,\texttt{使得对所有}\,n\ge n_0 \,\texttt{有}\, 0 \le cg(n) < f(n)\} \] 这等价于 \[ \lim\limits_{n \to +\infty} \dfrac{f(n)}{g(n)} = +\infty \] 例子：\(f(n) = n^{\frac{5}{4}} = \omega(n)\)

但是 \(f(n) = n^4 +1 \ne \omega (n^4)\) ，因为 \(n^4 = \Omega (n^4)\) 是渐进紧确的。

渐进记号的性质与比较

记号	含义	通俗理解
\(\Theta\)	紧渐进界	\(=\)
\(O\)	渐进上界	\(\le\)
\(o\)	非紧上界	\(<\)
\(\Omega\)	渐进下界	\(\ge\)
\(\omega\)	非紧下界	\(>\)

传递性

\[ \begin{aligned} f(n) = \Theta(g(n)) &\land g(n) = \Theta(h(n)) &\Rightarrow&\quad f(n) = \Theta(h(n)) \\f(n) = O(g(n)) &\land g(n) = O(h(n)) &\Rightarrow&\quad f(n) = O(h(n)) \\f(n) = \Omega(g(n)) &\land g(n) = \Omega(h(n)) &\Rightarrow&\quad f(n) = \Omega(h(n)) \\f(n) = o(g(n)) &\land g(n) = o(h(n)) &\Rightarrow&\quad f(n) = o(h(n)) \\f(n) = \omega(g(n)) &\land g(n) = \omega(h(n)) &\Rightarrow&\quad f(n) = \omega(h(n)) \end{aligned} \]