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

渐进记号

用来表示算法的渐进运行时间的记号是用定义域为自然数集的函数来定义的，这些记号便于用来表示最坏情况运行时间，因为一般仅定义于整数的输入规模上。

记号（紧渐进界）

对于记号有如下的定义：

记号限制一个函数在常数因子内，如图所示，是最小的可能值。如果存在正常数使得在右边的值永远在与之间，那么可以写成。

O记号（渐进上界）

对于记号有如下的定义：

记号给出一个函数在常数因子内的上限。如图所示，是最小的可能值。如果存在正常数使得在右边的值永远等于或小于，那么可以写成。

Ω记号（渐进下界）

对于记号有如下的定义：

1544506062143.png

记号给出一个函数在常数因子内的下限。如图所示，是最小的可能值。如果存在正常数使得在右边的值永远等于或大于，那么可以写成。

o记号（渐进非紧上界）

记号所提供的渐进上界可能是紧的，但也有可能不是。例如，是一个紧的上界，但却不是一个紧的上界。于是，我们使用记号来表示一个紧的上界。

对于记号有如下的定义：

例如，，但。

记号与记号的定义是类似的，主要区别在于对于，界对某个常数成立即可，而对于，界对所有常数成立。

记号（渐进非紧下界）

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

对于记号有如下的定义：

例如，，但。

函数间的比较

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

解递归式的三种方法

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

• 代换法：先猜某个界存在，然后用数学归纳法证明该猜测的正确性。
• 递归树方法：将递归式转换成树形结构，树中的节点代表在不同递归层次付出的代价。
• 主方法：给出递归形式的界，其中，是给定的函数。这种方法要记忆三种情况，就可以确定很多简单递归式的界了。

代换法

用代换法解递归式需要两个步骤：

1. 猜测解的形式。
2. 用数学归纳法找出使解真正有效地常数。

递归树方法

虽然代换法给递归式的解的正确性提供了一种简单的证明方法，但是有的时候很难得到一个好的猜测。此时，画出一个递归树是一种得到好猜测的直接方法。

设，则使用递归树求解该递归式的过程如下图所示：

主方法

设，为一函数，由递归式

对非负整数定义，那么有如下的渐进界：

求解和式时有一个比较常用的公式，假设是单调递增的函数，那么有如下的性质：