CHAPTER1 函数的增长与递归式

本文来自我的个人博客 https://www.zhangshenghai.com/posts/36105/

渐进记号

用来表示算法的渐进运行时间的记号是用定义域为自然数集 $N=\{ 0, 1, 2, ...\}$ 的函数来定义的，这些记号便于用来表示最坏情况运行时间 $T(n)$ ，因为 $T(n)$ 一般仅定义于整数的输入规模上。

$\Theta$ 记号（紧渐进界）

对于 $\Theta$ 记号有如下的定义：

$\Theta$ 记号限制一个函数在常数因子内，如图所示， $n_0$ 是最小的可能值。如果存在正常数 $n_0, c_1, c_2$ 使得在 $n_0$ 右边 $f(n)$ 的值永远在 $c_1g(n)$ 与 $c_2g(n)$ 之间，那么可以写成 $f(n) = \Theta(g(n))$ 。

O记号（渐进上界）

对于 $O$ 记号有如下的定义：

$O$ 记号给出一个函数在常数因子内的上限。如图所示， $n_0$ 是最小的可能值。如果存在正常数 $n_0, c$ 使得在 $n_0$ 右边 $f(n)$ 的值永远等于或小于 $cg(n)$ ，那么可以写成 $f(n) = O(g(n))$ 。

Ω记号（渐进下界）

对于 $Ω$ 记号有如下的定义：

1544506062143.png

$Ω$ 记号给出一个函数在常数因子内的下限。如图所示， $n_0$ 是最小的可能值。如果存在正常数 $n_0, c$ 使得在 $n_0$ 右边 $f(n)$ 的值永远等于或大于 $cg(n)$ ，那么可以写成 $f(n) = Ω(g(n))$ 。

o记号（渐进非紧上界）

$O$ 记号所提供的渐进上界可能是紧的，但也有可能不是。例如， $2n^2=O(n^2)$ 是一个紧的上界，但 $2n=O(n^2)$ 却不是一个紧的上界。于是，我们使用 $o$ 记号来表示一个紧的上界。

对于 $o$ 记号有如下的定义：

例如， $2n=o(n^2)$ ，但 $2n^2 \neq o(n^2)$ 。

$O$ 记号与 $o$ 记号的定义是类似的，主要区别在于对于 $f(n)=O(g(n))$ ，界 $0 \leq f(n) \leq cg(n)$ 对某个常数 $c>0$ 成立即可，而对于 $f(n)=o(g(n))$ ，界 $0 \leq f(n) \leq cg(n)$ 对所有常数 $c>0$ 成立。

$ω$ 记号（渐进非紧下界）

$ω$ 记号与 $Ω$ 记号的关系就与前面小o和大o之间的关系是类似的，我们用 $ω$ 记号表示一个紧的下界。

对于 $ω$ 记号有如下的定义：

例如， $n^2/2=ω(n)$ ，但 $n^2/2\neqω(n^2)$ 。

函数间的比较

实数的许多关系属性可以用于渐进比较，以上的记号之间具有传递性和对称性，下面假设 $f(n)$ 和 $g(n)$ 是渐进正值函数。

解递归式的三种方法

求解递归式，即找出解的渐进“ $\Theta$ ”或“ $O$ ”界的方法主要有三种：

代换法：先猜某个界存在，然后用数学归纳法证明该猜测的正确性。
递归树方法：将递归式转换成树形结构，树中的节点代表在不同递归层次付出的代价。
主方法：给出递归形式 $T(n) = aT(n/b)+f(n)$ 的界，其中 $a \geq 1, b>1$ ， $f(n)$ 是给定的函数。这种方法要记忆三种情况，就可以确定很多简单递归式的界了。