证明asymptotic notations（渐近记号）成立的正确方法是什么？

原有方法的核心问题 #

随机尝试c和n的取值验证的方法本质不成立，原因有两个：

• 所有渐近记号描述的都是n趋向无穷大时的函数增长趋势，小n的取值完全不影响结论，例2中测试的n=5、n=6都是极小值，不具备参考性
• 定义要求不等式对所有n≥n0都成立，而非仅对某几个采样的n成立，例1中仅验证了n=3的情况，但sin(n)和cos(n)都是周期震荡函数，会反复出现负值和零点，无法找到固定的n0使得不等式对所有更大的n都成立，所以该命题实际为假，采样验证刚好踩中了成立的个例

通用证明步骤 #

第一步：明确对应记号的定义要求 #

先把要证明的命题转换为严格的量化条件，不同渐近记号的核心要求如下：

• f(n) = O(g(n))：存在正的常数c、n0，对所有n≥n0，满足0 ≤ f(n) ≤ c·g(n)
• f(n) = Ω(g(n))：存在正的常数c、n0，对所有n≥n0，满足0 ≤ c·g(n) ≤ f(n)
• f(n) = Θ(g(n))：同时满足上述两个条件
• f(n) = o(g(n))：对任意正的常数c，都存在n0，对所有n≥n0，满足0 ≤ f(n) < c·g(n)
• f(n) = ω(g(n))：对任意正的常数c，都存在n0，对所有n≥n0，满足0 ≤ c·g(n) < f(n)

注意：o、ω类记号要求对任意c成立，而非仅找到某一个c，这是高频出错点

第二步：优先用极限法快速判定结论 #

对于单调非负的函数比较，直接算极限是效率最高的方法，完全不需要提前试值：

• 若lim(n→∞) f(n)/g(n) = L > 0，则f(n)=Θ(g(n))，同时属于O(g(n))、Ω(g(n))
• 若lim(n→∞) f(n)/g(n) = 0，则f(n)=o(g(n))，同时属于O(g(n))
• 若lim(n→∞) f(n)/g(n) = +∞，则f(n)=ω(g(n))，同时属于Ω(g(n))

以例22^√(lgn) = ω(lgn)为例，做两次换元即可快速算出极限：

1. 令t = lgn，当n→∞时t→∞，原式转换为求lim(t→∞) 2^√t / t
2. 令u = √t，当t→∞时u→∞，原式转换为求lim(u→∞) 2^u / u² = +∞
   直接就能得出命题为真的结论。

第三步：代数变形后构造c和n0（需严格按定义证明时使用） #

如果要求严格按照定义给出c和n0的取值，先对不等式做等价变形，把复杂运算降阶后再构造：
还是以例2为例，要证明对任意c>0，存在n0，n≥n0时2^√(lgn) > c·lgn：

1. 两边都是正数，取自然对数做等价变形，得到√(lgn) · ln2 > lnc + ln(lgn)
2. 结合第二步的极限结论，√t的增长速度远快于lnt，因此只要取t0 = lgn0足够大，就能让不等式成立，比如取t0 = (max(ceil(lnc / ln2), 10))²，对应的n0 = 2^t0即可满足条件。

常见注意事项 #

• 渐近记号的适用前提是两个函数均为非负，且n足够大时都有确定取值，周期震荡、反复出现负值的函数（比如sin(n)、cos(n)）一般不做渐近比较
• 不要用小n的采样结果推导结论，渐近性质和n较小的取值完全无关

内容的提问来源于stack exchange，提问作者Jack