多角度透彻理解渐近表示法(大O表示法)

若觉得本文写得还可以，请多多关注本人所作书籍《C++语法详解》电子工业出版社出版，网盘地址：
https://pan.baidu.com/s/1dIxLMN5b91zpJN2sZv1MNg

本文为原创文章，转载请注明出处，或注明转载自“黄邦勇帅(原名：黄勇)

本文后续文章是《透彻理解时间复杂度》

〇、理解“渐近”思维

1、渐近可理解为“逐渐近似”的意思，含有两层意思，逐渐和近似。渐近表示法有大O、大Ω、大Θ、小o、ω表示法，这些表示法有多种不同的定义方式，详见后文。

2、现实示例理解渐近思维

现举一个简单的例子让大家明白渐近的思想，马拉松比赛，运动员A一开始就以100米冲刺的速度跑出，运动员B则始终以比较均衡的速度跑出。一开始，A把B远远的抛在身后，但随着距离的延长，A会由于冲刺时体力的过度消耗，需要对体力进行恢复，从而使速度变得比B更慢，此时，A与B的距离逐渐接近，最终，随着A体力的恢复，A与B的距离会保持在一个较小的范围内，而且他们的速度也会逐渐接近，并且会维持到终点，这时，我们可以这样描述

“当距离n达到某一数值N时，运动员A和B的速度渐渐的相近”，

以上描述可以启发我们使用以下的思维来分析运动员A的不规则速度，

当距离n足够大时，可以使用运动员B的速度来近似的分析运动速度不规则的运动员A的速度，这就是渐近的思想

3、使用数学形式表示渐近思维

前文的渐近思维，并不是以数学形式来描述的，数学通常使用符号进行分析，而不是文字，因此，应把前文的文字描述符号化。

若以数学的形式来描述则需要解决以下问题：

1)、“逐渐”

• 渐近中近似需要满足一些条件，当满足这些条件时，才是近似的，也就是说，这种近似并不是一开始就是近似的，而是需要一个过程，是逐渐进行的，比如，前文马拉松比赛中的”达到一定距离“，可使用数学形式描述为当
  当n>N 时
  即，距离n大于N时，或描述为，距离n足够大时

2)、怎样近似

• 若使用数学描述就是，使用一个函数，如f，去近似描述另一个函数，如g。当然，f需要比g更简单，否则就会使问题变得更复杂。很显然，近似的目的是要使问题简化，而不是更复杂

3)、近似的程度。

• 若函数f和g是近似的，那么应怎样来描述近似的程度呢？渐近表示法使用了3种近似的程度，即大于等于、小于等于、等于(注意：并非完全相等，而是近似的相等），因此，函数f和g的近似程度可描述为
  f≥ g,f≤ g，f=g
  在这里，大家可能会觉得这种比较大小的关系没什么用，其实这种关系可用于进行粗略的比较，很多时候，这种比较就已经足够了，比如，当距离达到50km后，运动员A的速度v一定小于20km/小时，则可描述为
  当n>50时，v < 20
  从以上描述，至少可以得到运动员A的速度一定是小于20km/小时的，当然，以上仅是使用数字进行的描述，若使用函数，仍可进行相应的描述，假设f是关于x的函数，若有以下表述

  当x>N时，f(x)<= $x^2$

  则我们至少可以得出结论，当x大于N时，f(x)的增长速度会比$x^2$小。
  再如

  当x>N时，f(x)>=$x^2$
  当x>N时，g(x)>=x

  那么，我们可得出以下结论，当x>N时，f(x)比g(x)增长得更快。

4)、总结

• 通过以上的讲解，使用数学形式的渐近表示法大致可描述为(精确的数学定义详见后文正文)

  当x>N时，若有f(x)<=g(x)，或f(x)>=h(x)，或f(x) = j(x)

  则当x>N时，可使用g(x)、h(x)、j(x)来渐近的描述f(x)，当然，满足条件的g(x)、h(x)或j(x)非常多，以f(x)<=g(x)为例，凡是大于等于f(x)的函数都可用来描述f(x)。从此处也可以看到，所谓的渐近表示法，最终是一个不等式，因此，渐近表示法或多或少与不等式有一定关系，或者说就是一个不等式。

一、渐近表示法的定义

1、渐近表示法有多种不同的定义方式，下面分别讲解

2、不等式定义方式

• 定义1 (大O表示法)：
  • 若存在正常数c和N，对于所有的n ≥ N ，有0 ≤ f (n) ≤ c ∙ g(n)，则称f(n) = O( g(n) )
• 定义2 (大Ω表示法)：
  • 若存在正常数c和N，对于所有的n ≥ N，有0 ≤ c ∙ g(n)≤ f(n)，则称f (n)=Ω(g(n))
• 定义3 (大Θ表示法)：
  • 当且仅当f (n) = O(g(n))，且f (n) = Ω(g(n))时，f (n) =Θ(g(n))。也可表述为，若存在正常数c1、c2和N，对于所有的n ≥ N，有0 ≤ c1 ∙ g(n) ≤ f (n) ≤ c2 ∙ g(n)，则称f(n)=Θ(g(n))
• 定义4 (小o表示法)：
  • 若对任意正常数c > 0，存在常数N > 0，对于所有的n ≥ N，有0 ≤ f (n) < c ∙ g(n)， 则称f (n) = o(g(n))。也可表述为，若f (n) = O(g(n))，且f (n) ≠ Θ(g(n))，则f(n) = o (g(n))
• 定义5 (ω表示法)：
  • 若对每一个正常数c > 0，存在常数N >0 ，对于所有的n≥N，有0 ≤ f (n) < c ∙ g(n)，则称f(n)=ω(g(n))。也可表述为，若f (n) = Ω(g(n))，且f (n)≠ Θ (g(n))，则f (n)= ω(g(n))

3、集合定义方式

• 定义6 (大O表示法)：O( g(n) )表示以下函数的集合：
  • O(g(n))={f(n)：若存在正常数c和N，对于所有的n ≥ N，有0 ≤ f (n) ≤ c ∙ g(n) }
• 定义7 (大Ω表示法)：Ω(g(n) )表示以下函数的集合：
  • Ω( g(n))= { f (n)：若存在正常数c和N，对于所有的n≥ N，有0 ≤ c ∙ g(n)≤ f (n) }
• 定义8 (大Θ表示法)：Θ(g(n)表示以下函数的集合：
  • Θ(g(n))={ f (n)：若存在正常数c1、c2和N，对于所有的n≥N，有0≤c1∙g(n)≤f (n)≤ c2∙g(n) }
• 定义9(小o表示法)：o(g(n)表示以下函数的集合：
  • o(g(n))= { f (n)：若对任意正常数c>0，存在常数N>0，对于所有的n≥N，有0≤f (n)<c∙g(n) }
• 定义10 (ω表示法)：ω(g(n)表示以下函数的集合：
  • ω(g(n))={ f(n)：若对任意正常数c>0，存在常数N>0，对于所有的n≥N，有0≤c∙g(n)< f (n) }

4、对定义的补充说明

1)、函数定义域问题

• 描述算法时间/空间复杂度的函数T(n)通常是定义在整数输入规模上的，因此，本文的渐近表示法是根据定义域为自然数集N={0，1，2，…}的函数来定义的，这样的话，使用渐近表示法来描述T(n)就会很方便。当然，根据实际使用情况，也可将渐近表示法扩展到实数域的范围，或其他集合范围内。除非特别说明，本文所讲解的渐近表示法都是在自然数集N的范围内定义的。

  2)、n ≥ N的问题

• 渐近表示法的定义中都有一个“n≥N”的条件，这个条件是不可缺少的，可使用文字描述为“有足够大的n”或“当n足够大时”，也可使用如下形式来描述
  f(n)=O(g(n))，n ≥ N
  在数学意义上的渐近表示法，并不一定要求必须是n≥N，也可以是其他条件，比如，n ≤ N，n→∞，n→0等条件，本文主要讨论算法中使用的渐近表示法，因此，条件限定为n ≥ N。

  3)、f (n)和g(n)大于等于0的问题

• 由于算法的时间/空间复杂度都是大于等于0的函数，因此，本文把渐近表示法的定义限定为大于等于0的函数，作此限定之后更方便描述和讲解，否则，大O表示法中的0≤ f (n) ≤ c ∙ g(n)，应描述为 | f (n) | ≤ c ∙ | g(n) | ，其余渐近表示法类似。

二、理解渐近表示法的定义

1、使用集合的思维理解渐近表示法

1)、由定义6可见，O(g(n))并不代表单个函数f(n)，而是代表的，当n足够大时，满足f (n) ≤ c ∙ g(n)的所有函数 f(n)的集合，由集合理论可知，可表示为f (n)∈O(g(n))。定义1的主要作用在于可以把集合符号“∈”使用常用的“=”来代替，因此，f (n) ∈O(g(n)可表示为f(n)=O(g(n))，特别注意，这里的“=”是单向的，也就是说O(g(n))≠ f(n)，这是很明显的。

2）、不等式与集合

• 假设a为自然数，且a < 5，则该不等式表明，左侧a的值是小于5的某一个自然数，或者说，a是集合{0, 1, 2, 3, 4 }之中的某个值，也就是说a ∈{0, 1, 2, 3, 4 }，若使用O(5)来表示集合{0, 1, 2, 3, 4}，即O(5)表示小于5的自数然集，则a的值可表示为a ∈ O(5) ，若使用等号代替∈，则得到a =O(5)，如果不等式两侧都是函数，并把O表示的意义稍作调整，便得到所定义的大O表示法。当然，不等式a<b右侧的b也可按如上方式理解。渐近表示法是属于a<5的情形，即，固定右侧来分析左侧，因此，f (n)=O(g(n)) 表示 f(n)是不等式左侧的一个单个的函数，而O(g(n))代表的是小于等于c ∙ g(n)的一个函数集合。同理，对于等号，比如，a=b，其左侧和右侧也可按以上方式理解

3)、我们引进一种新的记号“L记号”来帮助理解O(g(n))，假设，L(n)表示一个绝对值小于n的数，但并不知道这个数具体是多少，此时的L(n)其实就是一个集合，但是，我们仍然可以使用L记号来进行一些推导，比如L(2) + L(4) = L(6)，L(1)+L(3) = L(4)等， L记号是一种不那么精确的记号，其实大O表示法(其他渐近表示法类似)也是一种不精确的记号，甚至比L记号更不精确。与L记号类似，若使用O(g(n))来代表某个数$x_n$ 的话，则表示，当n足够大时，该数一定满足 | $x_n$ | ≤ c ∙ | g(n)|，也就是说，当n足够大时，虽然不知道O(g(n))表示的具体的数，但可以估计出O(g(n))所要表示的数的大小一定小于等于c ∙ |g(n)|。

4)、由定义可见，Θ(g(n))是O(g(n))的子集，因此，若 f(n)=Θ(g(n)，则必有，f (n)=O(g(n)

2、图示法理解渐近表示法(见图1)，即，以“界”的思维理解渐近表示法

• 以大O表示法为例，由图1可见，当n足够大时，f (n)≤c ∙ g(n)，因此，可以认为当n足够大时(即，n ≥N时)，O(g(n))给出了f(n)的一个渐近上界(简称上界)，但这个上界并不要求多么紧确(或严密)，紧确的上界是指最小的上界，也就是说，O(g(n))是f(n)的一个渐近上界，但不一定是最小上界。同理，当n足够大时，Ω(g(n))给出了f(n)的一个渐近下界(简称下界)，Θ(g(n))给出了f (n)的一个渐近紧确界。
  
  3、以比较的思维理解渐近表示法
• 由渐近表示法的定义可见，渐近表示法其实就是在比较两个函数，因此，可把渐近表示法类比于两实数a和b间的比较，比如f(n)=o(g(n))，类比于a < b，此时称f (n)渐近小于g(n)，再如，f(n)=O(g(n))，类比于a ≤ b，称f(n)渐近小于等于g(n)。
• 注意，以上理解只是一种类比理解，这种理解比较粗糙，因为，任意两实数都是可以比较的，但并不是任意两个函数都可以使用渐近表示法进行比较，比如，不能使用渐近表示法来比较函数n和$n^{1+sinn}$，因为$n^{1+sinn}$的幂值在0~2之间摇摆，其值取于两者之间的所有值。

4、以近似估算的思维理解渐近表示法

• 渐近表示法的实质以及主要用途就是使用一个近似函数g(n)去估算原函数f(n)，当n足够大时，随着n增长时的近似变化趋势，并且可以根据这种趋势，对原函数进行近似比较。比如，假设f1(n) = O(n)，f2(n)=$O(n^2)$，可这样对f1(n)和f2(n)进行分析，当n足够大时，f1(n)不可能超过g1(n)=n的一个常数倍数，因此，f1(n)的增长趋势可使用g1(n)=n来近似估计，即，f1(n)是以g1(n)=n的形式近似线性增长的，同理，f2(n)是以g2(n)=$n^2$的形式近似平方级增长的，若对两函数进行比较，可以得出一个大致的近似的结论，当n足够大时，f1(n)增长得比f2(n)更慢。具体应用详见后文。
• 从上一点讲解可知，渐近表示法需要有一个可以增长的变量，比如O(n)，其中n就是判断函数增长的变量，即，当n足够大时，f(n)=O(n)。但，在实际使用中，经常使用O(1)来表示$O(n^0)$，这是一种活用方式。

5、大O表示法与小o表示法的区别(Ω表示法与ω表示法的区别类似)

• 定义上的区别，由定义可见，大O表示法和小o表示法的区别有两点
  • 正常数c的要求不同：大O表示法要求“存在c”使不等式f (n)≤c∙g(n)成立，而小o表示法要求“对所有的c”使不等式f(n)<c∙g(n成立。
  • 不等式不同，大O表示法是f(n)≤c∙g(n)，而小o表示法的不等式没有等号
• 大O表示法和小o表示法确定的界不同
  • 大O表示法提供的上界可能是渐近紧确的也可能不是，但小o表示法提供的上界一定是非渐近紧确的。

三、进一步理解大O表示法(其余渐近表示法的原理类似)

四、渐近表示法的证明方法

五、表达式中的渐近表示法

六、渐近表示法的应用

七、渐近表示法的性质

本文作者：黄邦勇帅(原名：黄勇)