渐进算法分析的定义（算法导论渐进记号Θ）

注意，此处的取值不唯一，只需要找到一组即可。这个上界的阶越低，评估越精确，越有价值。若存在正数c和，使得对一切，都有成立，则称f的渐进的下界是g，记作。例如，设，则f=Ω，取c=1,n_0=1即可f=Omega(n^2)，取c=1,n_0=1即可f=Omega(n^3)，取c=1,n_0=1即可，显然，O(n^3)作为上界更为精确。通俗理解为f低于g的阶。注意：这里定义中的c不再是存在量词而是全称量词，并且f取不到cg六、非渐进紧确下界：ω定义1：定义1：设f和g是定义域为自然数集N上的函数。

我们首先来明确一波这几个符号的读音和具体的含义：

• Θ：大Theta，渐进紧界，可类比于等号（=）
• O：字母大O，渐进上界，可类比于小于等于（<=）
• Ω：大Omega，渐进下界，可类比于大于等于（>=）
• o：字母小o，非渐进紧确上界，可类比于小于（<）
• ω：小omega，非渐进紧确下界，可类比于大于（>）

定义：存在正常数，，使得对于所有的时，有，则f(n)属于集合，记作。作为代替，我们通常记。

f(n) = Θ(g(n))

假设算法A的运行时间表达式为：

假设算法B的运行时间表达式为：

当问题规模足够大的时候，例如n=100万，算法的运行时间将主要取决于时间表达式的第一项，其它项的执行时间只有它的几十万分之一，可以忽略不计。第一项的常数系数，随着n的增大，对算法的执行时间也变得不重要了。

所以，算法A的运行时间可以记为：；

算法B的运行时间可以记为：。

可以代入定义进行验证：（以为例）

此时，我们只需要取满足条件的即可，很容易找到，即当时，有，满足定义。注意，此处的取值不唯一，只需要找到一组即可。

定义：设f(n)和g(n)是定义域为自然数集N上的函数。若存在正数c和，使得对一切，都有成立，则称f(n)的渐进上界是g(n)，记作。通俗的说n满足一定条件范围内，函数f(n)的阶不高于函数g(n)。

f(n) = O(g(n))

根据符号O的定义，用它评估算法的负载得到的桌子是问题规模充分大事件的一个上界。这个上界的阶越低，评估越精确，越有价值。

例如，设，则

即可

即可，显然，作为上界更为精确，更有价值。

这里我们似乎就得到了Θ和O之间的关系，没错，那就是，我们可以由，可以看到这是一个不可逆的过程，也就是说，只能由推出，不能逆向推导。

定义：设f(n)和g(n)是定义域为自然数集N上的函数。若存在正数c和，使得对一切，都有成立，则称f(n)的渐进的下界是g(n)，记作。通俗的说n满足一定条件范围内，函数f(n)的阶不低于函数g(n)。

f(n) = Ω(g(n))

根据符号Ω的定义，用它评估算法的负载得到的桌子是问题规模充分大事件的一个下界。这个下界的阶越高，评估越精确，越有价值。

例如，设，则

f(n) = Ω(n)，取c=1,n_0=1即可

f(n) = Omega(n^2)，取c=1,n_0=1即可

f(n) =Omega(n^3)，取c=1,n_0=1即可，显然，O(n^3)作为上界更为精确。

这里我们似乎就得到了Θ和Ω之间的关系，没错，那就是，我们可以由，可以看到这是一个不可逆的过程，也就是说，只能由推出，不能逆向推导。

定理：当且仅当有f(n) = Ω(g(n))且f(n) = O(g(n))，可以推出f(n) = Θ(g(n))。

这就给我们一个1思路，我们直接求Θ，直接找可能会很困难，此时我们可以通过求渐进上界，渐进下界来确定渐进紧界。

定义1：定义1：设f(n) 和g(n) 是定义域为自然数集N上的函数。若对于任意正数c，都存在，使得对一切，都有成立，则称f(n)的渐进非紧确上界是g(n)，记作。通俗的说n满足一定条件范围内，函数f(n)的阶低于函数g(n)。

定义2：设f(n)和g(n)是定义域为自然数集合的函数。如果 ，那么。通俗理解为f(n)低于g(n)的阶。

注意：这里定义中的c不再是存在量词而是全称量词，并且f(n)取不到cg(n)

定义1：定义1：设f(n) 和g(n) 是定义域为自然数集N上的函数。若对于任意正数c，都存在，使得对一切，都有成立，则称f(n)的渐进非紧确下界是g(n)，记作。通俗的说n满足一定条件范围内，函数f(n)的阶高于函数g(n)。

定义2：设f(n)和g(n)是定义域为自然数集合的函数。如果 ，那么。通俗理解为f(n)高于g(n)的阶。

注意：这里定义中的c不再是存在量词而是全称量词，并且f(n)取不到cg(n)

Θ、O、Ω、o、ω关系图

1.算法导论 殷建平 译机械工业出版社

2.算法设计与分析 屈婉玲著

3.算法设计与分析 王秋芬吕聪颖著