原文: 函数渐近界及渐近符号介绍
date: 2020-12-24 22:39:04

前言

在在在计算机算法设计和复杂性分析中, 函数渐近界与算法复杂度分析有着很多联系.

比如我们在算法复杂度分析中最常见到的大O符号（Big O notation）, 同时它在数学中是有着严谨的定义和证明

本节内容主要是引申到函数的渐近, 对其概念, 性质及一些分析行为做一些补充, 包括:

• 函数渐近界和渐近符号的介绍
• 非渐近紧确界的简单介绍
• O,Ω,Θ 渐近符号的性质及其等价性
• 函数渐近比较的方式和示例
• 求渐近界的方法及示例分析

渐近界介绍

定义

函数的渐近界通常用渐近符号来表达, 也称渐近记号, 首先来看最为常见的三种:

O big-oh: upper bound 渐近上界

• 函数f(n) = O(g(n)): 当且仅当存在正常数c, n0, 使得n>=n0时, 有 f(n) <= c*g(n)

Ω big-omega: lower bound 渐近下界

• 函数f(n) = Ω(g(n)): 当且仅当存在正常数c, n0, 使得n>=n0时, 有 f(n) >= c*g(n)

Θ theta: average bound 平均界 || asymptotically tight bound 渐近紧确界(紧确/确: 表示严格) || 紧致界

• 函数f(n) = θ(g(n)): 当且仅当存在正常数c1, c2, n0, 使得当n>=n0时, 有c1*g(n) < f(n) <= c2*g(n)

**注意: **

• 有的渐近记号我用了多个中文描述或翻译, 是因为很多时候中文叫法也不太相同, 所以不要搞混了
• 当且仅当: “在，并且仅仅在这些条件成立的时候”的缩写，在英语中的对应标记为iff

借助这张图更为直观的理解一下

渐近符号对比.png

O(g(n))是一个集合, 所以实际上 f(n) ∈ O(g(n))
通常我们记作 f(n) = O(g(n)) 以表达相同的概念, 其它几个记号同理.

示例

举个例子.png

看一个简单的例子分析: f(n) = 2n+3 , 求它的渐近上界O

首先代入定义中的不等式, 即 2n+3 <= cg(n)

你可以代入数字一个一个去试, 但是比较简单的方法是把左边的低阶项提高然后放到右边

即: 2n + 3 <= 2n+3n ==> 2n + 3 <= 5n

• 其中c=5, g(n)=n;

**因为: ** 存在正常数c=5, 当n>=(n0=1)时, 使得不等式 2n + 3 <= 5n 恒成立, 满足O定义;

**所以: ** f(n)=O(n);

在这里可以看出, 对于不等式 2n+3 <= cg(n) 来说, 右边的cg(n)不止只有 5n 才满足定义

e.g. cg(n)可以是3n(c=3, n0=3), 100n(c=100, n0=1) 都是成立的.

甚至你可以写它的高阶 n^2(c=1, n0=3), 此时 f(n) = O(n^2) 这也是成立的, 所以只要满足定义即可

Ω和θ也可以结合其定义用类似的方法得到:

• f(n) = Ω(n)
• f(n) = θ(n)

注意理解 f(n) = O(n) 这种写法表达什么意思, 有时候还会描述成 2n+3=O(n) 这样的写法

可以简单总结一下, 对于上述例子来说:

函数阶.png

1. n右边的都可以说是f(n)的上界
2. n左边的都可以说是f(n)的下界
3. 中间n就是平均界

你可以选择更为高阶的g(n)作为上界, 但那并不实用, 所以我们通常倾向于选择最为接近的g(n)来作为上界; 下界的选择同理.

分析

从上面这个梨子, 我们直观感觉到, 似乎通过以下3步就能满足渐近记号定义中的不等式:

1. 去掉低阶项并忽略高阶项的系数
2. O定义中的常量c取一个稍大于f(n)最高阶项系数的值
3. Ω定义中的常量c取一个稍小于f(n)最高阶项系数的值

这种感觉是很实用的, 下面来用一个函数f(n)来验证下: 从已知f(n)与θ反证定义中的c1, c2, n0

• f(n) = 0.5n^2 - 3, f(n) = θ(n^2)

所以只要存在正常量c1, c2, n0, 使得所有n>n0时, 满足:

• c1n^2 <= 0.5n^2 - 3 <= c2n^2

这里假设取:

• c1=0.25, n>(n0=12)
• c2=0.5, n>(n0=0)

此时存在c1, c2, 使得当n > (n0=12) 时满足不等式 0.25n^2 <= 0.5n^2 - 3 <= 0.5n^2

这里可以运用一些去通项来化简不等式, 既而得到c1, c2, n0 (满足存在即可, 并不是唯一)

这里用一个更直观的方式看看:

xy图.png

理解了简单的渐近界的分析方法, 那么它们三个的关系就可以用下面这个定理来表达:

• 对任意两个函数f(n)和g(n), 我们有f(n)=θ(g(n)), 当且仅当f(n)=O(g(n))且f(n)=Ω(g(n))

例如: f(n)=an^2 + bn + c , f(n)=θ(n^2) ==> f(n)=O(n2) 且 f(n)=Ω(n2)

需要注意的是并不是从渐近确界得出渐近上界和下界, 而通常是用渐近上界和下界来证明渐近确界

**哪个对我们更有用? **

一开始我会有这两个疑问, 对于一个函数f(n)来说:

• 是否需要把它的三种渐近界都求出 ?
• 通常情况下我们更关注哪个更有用 ?

首先: 上面示例中的函数比较简单, 所以三种界都可以得到, 而在实际中, 并不一定(下面有这样的示例)

每当一个函数, 如果你能用Theta(θ)表达是最好的, 如过无法得到它, 那么可以用BigO或Omega(Ω)来表达上界或下界

原因也很简单, 因为θ能够表达一个相较O与Ω更紧密精确的界限

就像我在完全不懂手机价格行情的情况下要买一部手机,
它可以告诉我3000, 4000(市场平均)的价格, 也可以告诉我100(市场最低) 或是10w(市场最高)的价格.
虽然这几种回答都是正确的, 但很明显平均价对我来说更有用

所以: 在这3种描述记号中, 如果给到的是O与Ω, 那么对方就不会确定这是不是最为接近的表达,

因为它可能是一个接近的, 也可能是一个较大或较小的值, 所以如果能给到θ是最好的

非渐近紧确界

介绍

通过对上面渐近上界, 渐近下界, 渐近紧确界的了解, 非渐近紧确界的概念就很好理解了,

它也有对应的两个渐近记号o(小o) 与 **ω(小欧米伽) **: 用来表示非渐近紧确的上界和下界

上面介绍的O渐近上界与Ω渐近下界, 可能是渐近紧确的也可能不是渐近紧确的

例如对函数 f(n)=2n^2来说 { Ω(n^2), Ω(n), Ω(logn) } 都符合其渐近下界Ω的定义

Tip: 通常我们都会选择最接近的界, 因为它最实用

但是只有 Ω(n^2) 是渐近紧确的, 其余几个都是非渐近紧确的

所以渐近上界和下界又可细分为: 渐近紧确的 和 非渐近紧确的

定义

o: 非渐近紧确上界

• 函数f(n) = o(g(n)): 对任意正常数c, 存在n0, 使得n>=n0时, 有f(n) <= c*g(n)

ω: 非渐近紧确上界

• 函数f(n) = ω(g(n)): 对任意正常数c, 存在n0, 使得n>=n0时, 有f(n) >= c*g(n)

注意这里对正常数c的描述是"任意", 而不局限特定某个范围, 这也是与O与Ω的最明显区别

也可用极限函数来表述o与ω的定义:

o:

• 表示当n趋于无穷大时, f(n)相对g(n)来说非常非常非常小

ω:

• 表示当n趋于无穷大时, f(n)相对g(n)来说非常非常非常大

此外: 还有一种表述: f(n)∈ω(g(n)) 当且仅当 g(n)∈o(f(n))

渐近符号性质

基本性质

主要是这几个: 整体性, 自反性, 传递性, 对称性, 转置对称性

1. 整体性

注: Ω, O, θ都成立

If f(n) is O(g(n)), Then af(n) is O(g(n))

e.g. f(n) = 2n^2 + 5 is O(n^2)==> 10f(n) = f(20n^2 + 50) is O(n^2)

2. 自反性

f(n) is O(f(n))

e.g. f(n) = n^2 ==> f(n) is O(n^2)

有点奇怪, 但也比较好想, 因为一个函数的上限可以是任意大于等于它的函数, 所以一个函数可以是它自己的上限

3. 传递性

If f(n) is O(g(n)) and g(n) is O(h(n)) Then f(n) is O(h(n))

用文字来描述就是当函数g是函数f的上限, 并且函数h是函数g的上限, 那么函数h也是函数f的一个上限函数

e.g. f(n) = n , g(n) = n^2 , h(n) = n^3

n is O(n^2) and n^2 is O(n^3)

then n is O(n^3)

4. 对称性

注: 只在θ成立

If f(n) is θ(g(n)), Then g(n) is θ(f(n))

e.g. f(n) = n^2 , g(n) = n^2

Then: f(n) = θ(n^2), g(n) = θ(n^2)

5. 转置对称性

注: 只在Ω与O成立

If f(n) is O(g(n)), Then g(n) is Ω(f(n))

用文字描述就是: 如果函数f是函数g的上限, 那么b函数就是a函数的下限 (我是你哥哥, 你就是我弟弟)

e.g. f(n) = n , g(n) = n^2

Then n is O(n^2) and n^2 is Ω(n)

反之亦然: If f(n) = Ω(g(n)) Then g(n) is O(f(n))

其它性质

除此之外, 还有几个重要的性质

• If f(n) = O(g(n)) and f(n) = Ω(g(n)), Then f(n) = θ(g(n))

这个比较简单, 之前已经有这样的函数示例了

• 两个函数相加的界

If f(n) = O(g(n)) and d(n) = O(e(n)), Then f(n) + d(n) = O(Max(g(n), e(n)))

e.g. f(n) = n = O(n) , d(n) = n^2 = O(n^2)

Then f(n) + d(n) = n + n^2 = On^2()

• 两个函数相乘的界

If f(n) = O(g(n)) and d(n) = O(e(n)),

Then f(n) * d(n) = O((g(n) * e(n)))

因为这些性质的成立, 所以可以在两个函数f与g的渐近比较中与实数a与b的比较之间做一种类比:

例如: 若f(n) = O(g(n)), 则可称f(n)的渐近小于等于g(n)

它们在范围上类似的几何描述

几何描述.png

函数的渐近比较

方式 & 示例

通常有两种方式来比较两个渐近函数的大小:

1. 代入法
2. 两边套上log

代入法比较简单了, 代入数值去比较就可以了, 但缺点是你要代入足够多的数值才可以, 就不说了

示例: 比较 n^2 与 n^3

这里为了书写简便, 就不写函数的渐近表示了, 直接用函数表达式

所以来看下用套上log的方法, 用步骤来表示比较过程:

1. ——
2. ——
3. ——

可得结果, 前者小于后者

两边log的方式在处理复杂函数时比较有用, 上面这两个函数用肉眼就能判断大小了, 所以看着不明显

再来两个比较复杂的函数:

示例一:

比较 f(n) = n^2*logn 与 g(n) = n* (logn)^10

1. ——
2. ——
3. ——

可得前者 > 后者

示例二:

比较 与 (注: )

1. ——
2. —— (注: )
3. ——

忽略系数后是一样的, 所以就函数渐近程度比较来说两者相同

常用log公式

补充一些常用的log公式:

更多示例

几个求O, Ω, Θ的例子来加深理解

Case 1: f(n) = 2n^2 + 3n + 4

• 2n^2 + 3n + 4 <= ``2n^2 + 3n^2 + 4n^2
• 2n^2 + 3n + 4 <= 9n^2

**∵ **此时存在c=9, 使得当n>(n0=1)时满足不等式

∴f(n) = O(n^2)

同样, 可以得到f(n) = Ω(n^2) 与 f(n) = θ(n^2), 方法类似, 不在赘述

Case 2: f(n) = n^2logn + n

• 1*n^2logn <= n^2logn <= 10 * n^2logn

可以得到O, Ω, θ都是 n^2logn

Case 3: f(n) = n!

注: n! = n * (n-1) * (n-2) * ... * 3 * 2 * 1

• 1 * 1 * 1 * ... * 1 <= n! <= n * n * n * ... * n
• 1 <= n! <= n^n

可以得到f(n) = O(n^n) 与 f(n) = Ω(1), 无法得到θ

Case 4: f(n) = logn!

• log(1 * 1 * 1 * ... * 1) <= logn! <= log(n * n * n * ... * n)
• log1 <= logn! <= logn^n
• log1 <= logn! <= nlogn

可以得到f(n) = O(nlogn) 与 f(n) = Ω(1), 无法得到θ

从Case 3 和 Case 4可以看出, 函数f中都是阶乘函数, 只能得到上界和下界, 无法给出紧密界限

上面也说过, 能算出紧密界限当然是最好的, 当你不能用平均界限来表达一个函数时, 还可以描述它的上限或下限, 此时上限和下限就变得很有用了

总结

需要说明的是, 这个主题与函数一样都来源于数学

只不过算法分析领域中运用到了这些数学的东西, 但是二者并不等同

所以不要将它与算法复杂度分析中的最好, 最坏, 平均情况混淆起来, 不然你可能会很困惑.

因为函数渐近界的性质在算法分析中有着重要应用, 所以了解这部分内容会对于理解渐近分析会有所帮助

对于这部分内容, 算是简单的理解和总结, 更多细致的内容需要运用极限的理论给予严格的数学证明, 这里并不涉及

所以理解上面的理论定义和示例分析对我来说已完全足够, 对通常的算法分析来说也已完全足够,

甚至不了解这部分内容也不会对你做算法分析有什么大的影响.

摘自:

• 部分内容来自《算法导论》第3章: 函数的增长