0301渐进记号-函数的增长-算法导论第三版

本文主要是介绍0301渐进记号-函数的增长-算法导论第三版，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1、前言

用来描述算法渐进运行时间的记号根据定义域为自然数集 N = { 0 , 1 , 2 , ⋯ } N=\{0,1,2,\cdots\} N={0,1,2,⋯}的函数来定义。这样的记号对描述最坏情况下的运行时间函数T(n)是方便的，因为该函数通常只定义在整数输入规模上。然而，我们发现有时按各种方式活用渐进记号是方便的。例如，我们可以扩展该记号到实数域或者选择性地限制其到自然数的一个子集。然而，我们应该确保能理解该记号的精确含义，以便在活用时不会误用它。本节将定义一些基本的渐进记号，并介绍一些常见的活用法。

2、渐进记号、函数与运行时间

我们主要使用渐进记号来描述算法的运行时间，渐进记号实际上应用于函数。回顾一下，我们曾把插入排序的最坏情况运行时间刻画为$a{n}^2+bn+c,其中a、b和c$是常量。通过把插入排序的运行时间写成$\Theta (n^2)$,我们除去了该函数的某些细节。因为渐进记号适用于函数，我们所写成的$\Theta (n^2)$就是函数$a{n}^2+bn+c$，所以上述情况碰巧刻画了插入排序的最坏情况运行时间。

我们使用渐进记号的函数通常刻画算法的运行时间，也可刻画算法的其他方面（例如，算法使用的空间数量）。

我们使用渐进记号的函数完全适合刻画任何输入的运行时间，不仅仅是最坏情况下的运行时间。

3、$\Theta$记号

插入排序最坏情况下运行时间为$T(n)=\Theta (n^2)$,下面定义这个记号。对于一个给定的函数$g(n),用\Theta (g(n))$来表示一下函数的集合
Θ [ g ( n ) ] = { f ( n ) : 存在正常量 c 1 , c 2 和 n 0 ， 使得对所有 n ≥ n 0 , 有 0 ≤ c 1 g ( n ) ≤ f ( n ) ≤ c 2 g ( n ) } \Theta[g(n)]=\{f(n):存在正常量c_1,c_2和n_0，\\ 使得对所有n\ge n_0,有\\ 0\le c_1g(n)\le f(n)\le c_2g(n)\} Θ[g(n)]={f(n):存在正常量c1​,c2​和n0​，使得对所有n≥n0​,有0≤c1​g(n)≤f(n)≤c2​g(n)}
若存在正常量$c_1和c_2$，使得对于足够大的n，函数$f(n)$能介入$c_{1}g(n)和c_{2}g(n)$之间，则$f(n)$属于集合$\Theta [g(n)]$。因为$\Theta [g(n)]$是一个集合，可以记$f(n)\in \Theta [g(n)]$,作为替代，我们通常记$f(n)=\Theta [g(n)]$表达相同概念。

上图1 为函数$f(n)=\Theta [g(n)]$。对于$n\ge n_0,c_{1}g(n)\le f(n)\le c_{2}g(n)$。换句话说，当$n\ge n_0$，在一个常量因子内$f(n)等于g(n)$。我们称$g(n)是f(n)$的一个 渐进紧确界。

$\Theta [g(n)]$的定义要求每个成员$f(n)\in \Theta [g(n)]$均为渐进非负,即当n足够大时，$f(n)$非负。（渐进正函数就是对于所有足够大的n均为正的函数）因此，函数$g(n)$本身必为渐进非负,复制集合$\Theta [g(n)]$为空。我们假设用在$\Theta$中的每个函数均渐进非负，对其他渐进记号成立。

示例1 使用形式化定义证明$\frac{1}{2}{n}^2-3n=\Theta (n^2)$
$$\begin{gathered} 证明：假设存在正常量c_1,c_2,n_0，使得对所有n\ge n_0,有 \\ {c}_1{n}^2\le \frac{1}{2}{n}^2-3n\le c_2{n}^2 \\ {n}^2除上式得 \\ {c}_1\le \frac{1}{2}-\frac{3}{n}\le c_2 \\ 如下图所示，对于n>0,c_2\ge \frac{1}{2},可以使不等式对于任何n\ge 1成立 \\ 取c_1\le \frac{1}{14},使左边不等式对于任何n\ge 7成立 \\ \therefore 令c_1=\frac{1}{14},c_2=\frac{1}{2},n_0=7 \end{gathered}$$

• 对于$0\le c_1\le \frac{1}{14},c_2\ge \frac{1}{2}$等式都是成立的，重要使得存在某个选择。

一个渐进正函数的低阶项在确定渐进确界是可以忽略，最高阶项的系数同样可以被忽略，因为它仅仅根据一个等于该系数的常量因子来改变$c_1和c_2$，证明参考书籍P27部分。

4、$\mathrm{O}$记号

$\Theta$记号渐进地给出了一个函数的上界和下界。当只有一个渐进上界时，使用$\mathrm{O}$记号。对于给定的函数$g(n)$，用$\mathrm{O}[g(n)]$,来表示函数的集合：

O [ g ( n ) ] = { f ( n ) : 存在正常量 c 和 n 0 , 使得对所有 n ≥ n 0 , 有 0 ≤ f ( n ) ≤ c g ( n ) } \Omicron[g(n)]=\{f(n):存在正常量c和n_0,使得对所有n\ge n_0,有0\le f(n)\le cg(n)\} O[g(n)]={f(n):存在正常量c和n0​,使得对所有n≥n0​,有0≤f(n)≤cg(n)}

我们记$f(n)=\mathrm{O}[g(n)]$以指出函数$f(n)$是集合$\mathrm{O}[g(n)]$的成员。注意，$f(n)=\Theta [g(n)]$蕴含着$f(n)=\mathrm{O}[g(n)]$，因为$\Theta$是一个比$\mathrm{O}$记号更强的一个概念（范围更小）。按集合论的写法，我们有$\Theta [g(n)]\subseteq \mathrm{O}[g(n)]$。

既然$\mathrm{O}$描述上界，那么当用它来限制算法的最坏情况下运行时间时，关于算数在每个输入上的云之家，我们也有一个界，这就是前面讨论的综合性论述。因此，对插入排序的的最坏情况运行时间的界$\mathrm{O}(n^2)$也适用于对每个输入的运行时间。然而，对插入排序的最坏情况运行时间的界$\Theta (n^2)$并未暗示插入排序对每个输入的运行时间的界也是$\Theta (n^2)$。例如当输入以排好序时，插入排序的运行时间为$\Theta (n)$。

从技术上看，称插入排序的运行时间为$\mathrm{O}(n^2)$有点不合适，因为对给定的n，实际的运行时间是变化的，依赖于规模为n的特定输入。当我们说运行时间为$\mathrm{O}(n^2)$时，意指存在一个$\mathrm{O}(n^2)的函数f(n)$，使得对n的任意值，不管选择的什么特定的规模为n的输入，其运行时间的上界都是$f(n)$。

5、$\Omega$记号

$\mathrm{O}$记号提供了一个函数的渐进上界，$\Omega$记号提供了 渐进下界。对于给定的函数$g(n)$，用$\Omega [g(n)]$表示一下函数的集合：

Ω [ g ( n ) ] = { f ( n ) : 存在正常数 c 和 n 0 , 使得对所有 n ≥ n 0 ，有 0 ≤ c g ( n ) ≤ f ( n ) } \Omega[g(n)]=\{f(n):存在正常数c和n_0,使得对所有 n\ge n_0，有0\le cg(n)\le f(n)\} Ω[g(n)]={f(n):存在正常数c和n0​,使得对所有n≥n0​，有0≤cg(n)≤f(n)}

6、定理3.1

定理3.1 对任意两个函数$f(n)和g(n)$，我们有$f(n)=\Theta [g(n)]$，当且仅当$f(n)=\mathrm{O}[g(n)]和f(n)=\Omega [g(n)]$.

7、等式和不等式中的渐进记号

当渐进记号独立于等式（或不等式）的右边（即不在一个更大的公式内）时，如在$n=\mathrm{O}(n^2)$中，我们已经定义等号意指集合的成员关系；$n\in \mathrm{O}(n^2)$。

当渐进记号出现在某个公式中时，我们将其解释为代表某个我们不关注名称的匿名函数。

• 示例：公式$2n^2+3n+1=2n^2+\Theta (n)$,意指$2n^2+3n+1=2n^2+f(n),f(n)是集合\Theta (n)$的中的某个函数。
• 作用：消除一个等式中无关紧要的细节和混乱。例如，归并排序中最坏情况运行时间表示为递归式$T(n)=2T(\frac{n}{2})+\Theta (n)$.

一个表达中的匿名函数的数目可以理解为等于渐进记号出现的次数。

• 示例：在表达式${\sum }_{i=1}^n\mathrm{O}(i)$中，只有一个匿名函数（一个i的函数）。因此，这个表达式不等于$\mathrm{O}(1)+\mathrm{O}(2)+\cdots +\mathrm{O}(n)$，后者没有一个清晰的解释。

当渐进记号出现咋等式的左边意指：物流怎么样选择等号左边的匿名函数，总有一种方法来选择等号右边的匿名函数使等式成立。

• 示例：$2n^2+\Theta (n)=\Theta (n^2)$,对任意函数$f(n)\in \Theta (n)$，存在某个函数$g(n)\in \Theta (n^2)$，使得对所有的n，有$2n^2+f(n)=g(n)$

等式右边比左边提供的细节更 粗糙。

示例：$2n^2+3n+1=2n^2+\Theta (n)=\Theta (n^2)$
KaTeX parse error: Can't use function '$' in math mode at position 177: …)=h(n)\\ 这种解释包含$̲2n^2+3n+1=\Thet…

8、$o$记号

由$o$记号提供的渐进上界可能是也可能不是渐进紧确的。界$2n^2=\mathrm{O}(n^2)$是渐进紧确的，当是界$2n=\mathrm{O}(n^2)$不是。我们使用$o$记号来表示一个非渐进紧确的上界。形式化定义$o[g(n)]$为一下集合：

ο [ g ( n ) ] = { f ( n ) : ∀ c > 0 , ∃ n 0 , 当 n ≥ n 0 , 有 o ≤ f ( n ) < c g ( n ) } \omicron[g(n)]=\{f(n): \forall c\gt 0,\exist n_0,当n\ge n_0,有o\le f(n)\lt cg(n)\} ο[g(n)]={f(n):∀c>0,∃n0​,当n≥n0​,有o≤f(n)<cg(n)}

9、$\omega$记号

$\omega$记号与$\Omega$记号的关系类似于$o$记号与$\mathrm{O}$记号的关系。我们使用$\omega$记号来表示一个非渐进紧确的下界，形式化的定义$\omega [g(n)]$为一下集合：

ω [ g ( n ) ] = { f ( n ) : ∀ c > 0 , ∃ n 0 , 当 n ≥ n 0 , 有 o ≤ c g ( n ) < f ( n ) } \omega[g(n)]=\{f(n): \forall c\gt 0,\exist n_0,当n\ge n_0,有o\le cg(n)\lt f(n)\} ω[g(n)]={f(n):∀c>0,∃n0​,当n≥n0​,有o≤cg(n)<f(n)}

10、比较各种函数

实数的许多关系性质也适用于渐进比较。下面假定$f(n)和g(n)$渐进为正。

10.1 传递性

• $f(n)=\Theta [g(n)]且g(n)=\Theta [h(n)]\Rightarrow f(n)=\Theta [h(n)]$
• $f(n)=\mathrm{O}[g(n)]且g(n)=\Theta [h(n)]\Rightarrow f(n)=\mathrm{O}[h(n)]$
• $f(n)=\Omega [g(n)]且g(n)=\Theta [h(n)]\Rightarrow f(n)=\Omega [h(n)]$
• $f(n)=\omega [g(n)]且g(n)=\Theta [h(n)]\Rightarrow f(n)=\omega [h(n)]$
• $f(n)=\omega [g(n)]且g(n)=\Theta [h(n)]\Rightarrow f(n)=\omega [h(n)]$

10.2 自反性

• $f(n)=\Theta [f(n)]$
• $f(n)=\mathrm{O}[f(n)]$
• $f(n)=\Omega [f(n)]$

10.3 对称性

• $f(n)=\Theta [g(n)]当且仅当g(n)=\Theta [f(n)]$

10.4 转置对称

• $f(n)=\mathrm{O}[g(n)]当且仅当g(n)=\Omega [f(n)]$
• $f(n)=o[g(n)]当且仅当g(n)=\omega [f(n)]$​

若$f(n)=o[g(n)]$，则称$f(n)$渐进小于$g(n)$；若$f(n)=\omega [g(n)]$，则称$f(n)$渐进大于$g(n)$；

实数的下列性质不适用于渐进记号

10.5 三分性

对于任意的实数a和b，下列三种情况恰有一种必然成立$a<b,a=b或者a>b$.

虽然任意两个实数都可以比较，但不是所有的函数都可渐进比较。

• 示例：$n和n^{1+\sin n}$。

结语

欢迎小伙伴一起学习交流，需要啥工具或者有啥问题随时联系我。

❓QQ:806797785

⭐️源代码地址：https://gitee.com/gaogzhen/algorithm

[1]算法导论(原书第三版)/(美)科尔曼(Cormen, T.H.)等著;殷建平等译 [M].北京:机械工业出版社,2013.1(2021.1重印).p25-30

[2]算法导论------渐近记号Θ、Ο、o、Ω、ω详解[CP/OL]

这篇关于0301渐进记号-函数的增长-算法导论第三版的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---