第四章 · 正整数变量的函数的极限

符号 OO、oo 与 ∼\sim

§89 30 分钟

一种比较两个数列增长或缩小快慢的简洁语言,它的运算规则,以及它那只能单向读的等号。

为什么重要

我们常常不需要确切地知道一个数列,只需要知道它与某个简单的东西相比有多大。100n2+1000n100n^2 + 1000n 是不是“大约是 n2n^2”?sin⁡n\sin n 是不是“与 nn 相比很小”?§89 引入了三个符号,使这样的说法既精确又简短:OO(“至多与……同阶”)、oo(“比……低阶”)和 ∼\sim(“同阶,并且比值有确定的极限”)。哈代说他要到后面的章节才会使用这些符号;如今它们已经是分析学、数论和计算机科学的日常语言。

基本想法

这三个符号说的都是比值 f(n)/ϕ(n)f(n)/\phi(n),其中 ϕ(n)\phi(n) 是某个用来作比较的简单数列,比如 11、nn 或 n2n^2:

  • f=O(ϕ)f = O(\phi):比值(的绝对值)保持有界。
  • f=o(ϕ)f = o(\phi):比值趋于 00。
  • f∼lϕf \sim l\phi:比值趋于一个极限 l≠0l \neq 0。

所以只要一幅图,即比值的图像,就能判定这三者。在很长的 nn 的范围内,最好把 nn 画在对数坐标上。

探索 比值赛跑

试一试:从 f=100n2+1000nf = 100n^2 + 1000n 开始,依次把它与 ϕ=n\phi = n、n2n^2 和 n3n^3 比较。然后把 sin⁡n\sin n 与 11 和 n\sqrt n 比较,再把 (2+(−1)n) n(2 + (-1)^n)\,n 与 nn 比较。

f(n)ϕ(n)=100n2+1000nn2\frac{f(n)}{\phi(n)} = \frac{100n^2 + 1000n}{n^2}
n(对数坐标)f/φ
  • f(n)/φ(n)
  • ±K,其中 K = 1100 是 n ≤ 10⁶ 时 |f/φ| 的最大值
  • 比值的极限:100
当 n=106n = 10^6 时,比值为 100。f=O(ϕ)f = O(\phi) ✓ · f=o(ϕ)f = o(\phi) ✗ · f∼lϕf \sim l\phi ✓,其中 l=100l = 100。比值趋于 100:f 与 φ 的增长速度相同,只差这个倍数。
留意什么

与 n2n^2 相比,比值稳定在 100100:同阶且比值有确定的极限,f∼100n2f \sim 100n^2。与 n3n^3 相比,比值逐渐消失(oo);与 nn 相比,它冲出了图的顶端(连 OO 都不是)。前面的项无关紧要:比值从 11001100 开始,但只有它最终的表现才算数。sin⁡n\sin n 和 (2+(−1)n)n(2 + (-1)^n)n 显示了 OO 与 ∼\sim 之间的差距:比值保持有界,却始终不稳定下来。

精确表述

在本节中,ϕ(n)\phi(n) 始终是正的、单调的(它单调不减或单调不增),所以它趋于 00、趋于一个正的极限,或者趋于 +∞+\infty。实际使用中,它是像 1/n1/n、11、nn 或 n2n^2 这样的东西。

定义 OO、oo 与 ∼\sim 哈代:§89 (i)–(iii)

设 f(n)f(n) 对所有充分大的 nn 有定义。

  • (i) 如果存在常数 KK,使得当 nn 充分大时都有 ∣f(n)∣≤Kϕ(n)|f(n)| \le K\phi(n),就记作 f=O(ϕ)f = O(\phi)。
  • (ii) 如果 f(n)/ϕ(n)→0f(n)/\phi(n) \to 0,就记作 f=o(ϕ)f = o(\phi)。
  • (iii) 如果 f(n)/ϕ(n)→lf(n)/\phi(n) \to l,且 l≠0l \neq 0,就记作 f∼lϕf \sim l\phi。

特别地,f=O(1)f = O(1) 表示 ff 有界,f=o(1)f = o(1) 表示 f→0f \to 0。

哈代自己举的例子:

n=O(n2),100n2+1000n=O(n2),sin⁡nθπ=O(1);n = O(n^2), \quad 100n^2 + 1000n = O(n^2), \quad \sin n\theta\pi = O(1); n=o(n2),100n2+1000n=o(n3),sin⁡nθπ=o(n);n = o(n^2), \quad 100n^2 + 1000n = o(n^3), \quad \sin n\theta\pi = o(n); n+1∼n,100n2+1000n∼100n2,n+sin⁡nθπ∼n;n + 1 \sim n, \quad 100n^2 + 1000n \sim 100n^2, \quad n + \sin n\theta\pi \sim n;

以及对于 a0≠0a_0 \ne 0、b0≠0b_0 \ne 0 的多项式,

a0np+a1np−1+⋯+apb0nq+b1nq−1+⋯+bq∼a0b0 np−q.\frac{a_0 n^p + a_1 n^{p-1} + \cdots + a_p}{b_0 n^q + b_1 n^{q-1} + \cdots + b_q} \sim \frac{a_0}{b_0}\, n^{p - q}.

注意,f=O(ϕ)f = O(\phi) 并不是说 ff 和 ϕ\phi 一样大,而只是说它的阶不比后者高:n=O(n2)n = O(n^2) 是对的。单独的符号 O(ϕ)O(\phi) 表示“某个未具体指明的、满足 f=O(ϕ)f = O(\phi) 的 ff”,这样我们就能写出 O(1)+O(1)=O(1)O(1) + O(1) = O(1) 这样的式子。

定理 符号的运算规则 哈代:§89
  • (1) O(ϕ)+O(ψ)=O(ϕ+ψ)O(\phi) + O(\psi) = O(\phi + \psi)。
  • (2) O(ϕ) O(ψ)=O(ϕψ)O(\phi)\,O(\psi) = O(\phi\psi)。
  • (3) O(ϕ) o(ψ)=o(ϕψ)O(\phi)\,o(\psi) = o(\phi\psi)。
  • (4) 如果 f∼ϕf \sim \phi,那么 f+o(ϕ)∼ϕf + o(\phi) \sim \phi。
  • (5) o(ϕ)=O(ϕ)o(\phi) = O(\phi),但 O(ϕ)=o(ϕ)O(\phi) = o(\phi) 不成立:这些“等式”只能从左往右读。

证明

证明 规则 (1)–(3)
思路

把每个符号翻译回关于比值的不等式或极限,组合起来,再翻译回去。

(1):有界加有界

如果当 nn 很大时 ∣f∣≤Kϕ|f| \le K\phi 且 ∣g∣≤Lψ|g| \le L\psi,那么 ∣f+g∣≤∣f∣+∣g∣≤Kϕ+Lψ≤max⁡(K,L)(ϕ+ψ)|f + g| \le |f| + |g| \le K\phi + L\psi \le \max(K, L)(\phi + \psi)。

(2):有界乘有界

对同样的 ff、gg:∣fg∣≤KL ϕψ|fg| \le KL\,\phi\psi。

(3):有界乘无穷小

如果 ∣f∣≤Kϕ|f| \le K\phi 且 g/ψ→0g/\psi \to 0,那么 ∣fgϕψ∣≤K∣gψ∣→0\left|\dfrac{fg}{\phi\psi}\right| \le K\left|\dfrac{g}{\psi}\right| \to 0,所以 fg=o(ϕψ)fg = o(\phi\psi)。

证明 (4) 与 (5)
思路

仍然用比值来做:加上一个与 ϕ\phi 之比趋于 00 的量,不会改变比值的极限;比值趋于 00 则必定有界,反之不然。

(4)

如果 f/ϕ→1f/\phi \to 1 且 g/ϕ→0g/\phi \to 0,那么 (f+g)/ϕ=f/ϕ+g/ϕ→1+0=1(f + g)/\phi = f/\phi + g/\phi \to 1 + 0 = 1。(同样的论证表明:只要 f∼lϕf \sim l\phi,就有 f+o(ϕ)∼lϕf + o(\phi) \sim l\phi。)

(5):oo 蕴涵 OO

如果 f/ϕ→0f/\phi \to 0,那么当 nn 很大时 ∣f/ϕ∣<1|f/\phi| < 1,所以当 nn 很大时 ∣f∣≤1⋅ϕ|f| \le 1 \cdot \phi:f=O(ϕ)f = O(\phi)。

(5):OO 不蕴涵 oo

f(n)=1f(n) = 1 是 O(1)O(1),但不是 o(1)o(1),因为它不趋于 00。所以“O(1)=o(1)O(1) = o(1)”是错的,而“o(1)=O(1)o(1) = O(1)”是对的:这里的等号表示“属于这一类”,而不是相等。

证明 两个多项式之比
思路

分子除以 npn^p,分母除以 nqn^q:除首项以外,每一项都带上 nn 的负幂,从而趋于 00。

改写比值

a0np+⋯+apb0nq+⋯+bq/np−q=a0+a1/n+⋯+ap/npb0+b1/n+⋯+bq/nq.\frac{a_0 n^p + \cdots + a_p}{b_0 n^q + \cdots + b_q} \Big/ n^{p-q} = \frac{a_0 + a_1/n + \cdots + a_p/n^p}{b_0 + b_1/n + \cdots + b_q/n^q}.

取极限

k≥1k \ge 1 时的每个 ak/nka_k/n^k 和 bk/nkb_k/n^k 都趋于 00,所以分子趋于 a0a_0,分母趋于 b0≠0b_0 \neq 0。由商的极限定理,比值趋于 a0/b0≠0a_0/b_0 \ne 0,这正是 ∼a0b0 np−q\sim \tfrac{a_0}{b_0}\, n^{p-q} 的定义。(分母这个多项式至多在有限多个 nn 处为零,而定义只涉及很大的 nn。)

例题与习题

习题 ●○○ 哈代:§89

判断 OO、oo、∼\sim 中哪些成立,以及相应的常数:(a) f=3n2−7n+2f = 3n^2 - 7n + 2 与 n2n^2 比较;(b) f=nsin⁡nf = n\sin n 与 nn 比较;(c) f=n2+1f = \sqrt{n^2 + 1} 与 nn 比较;(d) f=1/(n2+1)f = 1/(n^2 + 1) 与 1/n1/n 比较。

提示
在每种情形下计算 f/ϕf/\phi,看它是有界、趋于 00,还是趋于一个非零的极限。

解答

(a) f/n2=3−7/n+2/n2→3f/n^2 = 3 - 7/n + 2/n^2 \to 3:所以 f∼3n2f \sim 3n^2,f=O(n2)f = O(n^2),但不是 o(n2)o(n^2)。

(b) f/n=sin⁡nf/n = \sin n,有界,但(可以证明)没有极限:f=O(n)f = O(n),既不是 o(n)o(n),也不是 ∼ln\sim ln。

(c) f/n=1+1/n2→1f/n = \sqrt{1 + 1/n^2} \to 1:f∼nf \sim n(并且是 O(n)O(n))。

(d) f/(1/n)=n/(n2+1)→0f/(1/n) = n/(n^2 + 1) \to 0:f=o(1/n)f = o(1/n),实际上 f∼1/n2f \sim 1/n^2。

习题 有界项之和 ●○○ 哈代:§89

解释并证明公式 ∑r=1nO(1)=O(n)\sum_{r=1}^{n} O(1) = O(n)。

提示
要小心:这个界必须对每一项都相同。

解答

它的意思是:如果对每个 rr 都有 ∣ur∣≤K|u_r| \le K(所有的项共用一个常数 KK),那么 ∣u1+⋯+un∣≤Kn|u_1 + \cdots + u_n| \le Kn,所以 u1+⋯+un=O(n)u_1 + \cdots + u_n = O(n)。证明就是三角不等式:∣u1+⋯+un∣≤∣u1∣+⋯+∣un∣≤nK|u_1 + \cdots + u_n| \le |u_1| + \cdots + |u_n| \le nK。如果每一项只有它自己的界,这个命题就不成立:对每个固定的 rr,ur=ru_r = r 都是有界的,然而 1+2+⋯+n∼12n21 + 2 + \cdots + n \sim \tfrac12 n^2。

习题 ●●○ 哈代:§89

证明 n+1−n∼12n\sqrt{n+1} - \sqrt n \sim \dfrac{1}{2\sqrt n},并由此推出 n+1−n=o(1)\sqrt{n+1} - \sqrt n = o(1)。

提示
乘以并除以 n+1+n\sqrt{n+1} + \sqrt n。

解答

n+1−n=1n+1+n\sqrt{n+1} - \sqrt n = \dfrac{1}{\sqrt{n+1} + \sqrt n}。它与 1/(2n)1/(2\sqrt n) 之比是 2nn+1+n=21+1/n+1→1\dfrac{2\sqrt n}{\sqrt{n+1} + \sqrt n} = \dfrac{2}{\sqrt{1 + 1/n} + 1} \to 1。因此 n+1−n∼12n−1/2\sqrt{n+1} - \sqrt n \sim \tfrac12 n^{-1/2},又由于 n−1/2→0n^{-1/2} \to 0,它是 o(1)o(1)(实际上 =O(n−1/2)= O(n^{-1/2}),所以这个差趋于 00 的速度大约和 1/n1/\sqrt n 一样快)。

习题 ∼\sim 与减法不相容 ●●○ 哈代:§89

证明 f∼ϕf \sim \phi 和 g∼ϕg \sim \phi 蕴涵 f−g=o(ϕ)f - g = o(\phi),但并不蕴涵 f−g∼hf - g \sim h,不论你猜想的是哪个简单的 hh。举一个 f∼gf \sim g 但 f−gf - g 不是 o(1)o(1) 的例子。

提示
取 f=n+1f = n + 1,g=ng = n,ϕ=n\phi = n。

解答

如果 f/ϕ→1f/\phi \to 1 且 g/ϕ→1g/\phi \to 1,那么 (f−g)/ϕ→0(f - g)/\phi \to 0:所以 f−g=o(ϕ)f - g = o(\phi)。能说的也就只有这些:取 f=n+1f = n + 1,g=ng = n,有 f∼g∼nf \sim g \sim n,但 f−g=1f - g = 1,它不是 o(1)o(1)。取 f=n+nf = n + \sqrt n,g=ng = n,差是 n\sqrt n,它趋于无穷大。渐近等价说的是相对误差趋于 00;绝对误差可以是任何比 ϕ\phi 低阶的量。

自测

自测 判断对错

O(1)=o(1)O(1) = o(1)。

解析

错。把它读成“每个有界数列都趋于 00”,f(n)=1f(n) = 1 就推翻了它。另一个方向 o(1)=O(1)o(1) = O(1) 是对的:每个无穷小数列都有界。含 OO 和 oo 的等式要从左往右读。

自测 单项选择

关于 f(n)=100n2+1000nf(n) = 100n^2 + 1000n,下面哪个说法是错的?

解析

f/n2=100+1000/n→100f/n^2 = 100 + 1000/n \to 100,不是 00,所以 ff 不是 o(n2)o(n^2)。它是 O(n2)O(n^2)(比值有界),因而也是 O(n3)O(n^3)(OO 的说法可以放宽),并且 f∼100n2f \sim 100n^2。

自测 填一个数

如果 f(n)=6n3−n2n+5f(n) = \dfrac{6n^3 - n}{2n + 5},且 f∼ln2f \sim l n^2,那么 ll 是多少?

解析

看首项:6n3/(2n)=3n26n^3/(2n) = 3n^2,所以 l=6/2=3l = 6/2 = 3。严格地说,f/n2=6−1/n22+5/n→3f/n^2 = \dfrac{6 - 1/n^2}{2 + 5/n} \to 3。

自测 判断对错

(2+(−1)n) n=O(n)(2 + (-1)^n)\,n = O(n),但不存在 ll 使 (2+(−1)n) n∼ln(2 + (-1)^n)\,n \sim l n。

解析

对。它与 nn 之比是 1,3,1,3,…1, 3, 1, 3, \dots:以 33 为界,所以是 O(n)O(n);但它没有极限,所以任何 ∼\sim 的说法都不成立。OO 只需要一个界;∼\sim 需要比值有极限。

哈代的用语

小结

小结
  • f=O(ϕ)f = O(\phi):从某一项起 ∣f/ϕ∣|f/\phi| 有界。f=o(ϕ)f = o(\phi):f/ϕ→0f/\phi \to 0。f∼lϕf \sim l\phi:f/ϕ→l≠0f/\phi \to l \ne 0。
  • O(1)O(1) 表示有界,o(1)o(1) 表示趋于 00。只有最终的表现才算数。
  • oo 蕴涵 OO,反之不然;等号是单向的。
  • 规则:O+O=OO + O = O,O⋅O=OO \cdot O = O,O⋅o=oO \cdot o = o,并且加上 o(ϕ)o(\phi) 不改变 f∼ϕf \sim \phi。
  • 多项式之比 ∼\sim(首项系数之比)× n次数之差\times\, n^{\text{次数之差}}。