关于f(n)=Θ(g(n))与渐近等价性的疑问及证明正确性确认

一、Θ(g(n))和渐近等价的区别 #

首先明确两个核心概念：

• f(n)=Θ(g(n))：存在正常数(c_1)、(c_2)和(n_0)，当(n≥n_0)时，满足 ( c_1g(n) ≤ f(n) ≤ c_2g(n) )，核心是f和g的增长速度同阶，允许常数倍的差异。
• 渐近等价（(f(n) \sim g(n))）：要求 ( \lim_{n \to \infty} \frac{f(n)}{g(n)} = 1 )，这是Θ关系的特例——只有当两者的比值极限严格为1时才成立。

结论：若f(n)与g(n)渐近等价，则一定有(f(n)=Θ(g(n)))；但反过来不成立，比如(f(n)=2n)、(g(n)=n)，满足(f(n)=Θ(g(n)))，但比值极限为2≠1，不属于渐近等价。

二、四组时间复杂度的验证修正 #

A组：( f(n) = \log(n^{100}) )，( g(n) = \log(n^2) ) #

推导思路正确，但计算存在笔误：(\log(n^{100}) = 100\log n)，而非(\log(n^{200}))。正确极限为：
[
\lim_{n \to \infty} \frac{\log(n^{{100})}{\log(n}2)} = \lim_{n \to \infty} \frac{100\log n}{2\log n} = 50
]
结果是正的常数，符合Θ关系的极限判定规则，因此**(f(n)=Θ(g(n)))**成立。

B组：( f(n) = \sqrt{n} )，( g(n) = \log(n) ) #

极限计算正确：
[
\lim_{n \to \infty} \frac{\sqrt{n}}{\log n} = +\infty
]
说明f(n)增长远快于g(n)，无法找到上界常数(c_2)满足(\sqrt{n} ≤ c_2\log n)，因此**(f(n)≠Θ(g(n)))**。

C组：( f(n) = 3^n )，( g(n) = 5^n ) #

极限计算正确：
[
\lim_{n \to \infty} \frac{3^n}{5n} = \lim_{n \to \infty} \left( \frac{3}{5} \right)^n = 0
]
说明f(n)增长远慢于g(n)，无法找到下界常数(c_1)满足(c_1 \cdot 5^n ≤ 3^n)，因此**(f(n)≠Θ(g(n)))**。

D组：( f(n) = \sin(n)+3 )，( g(n) = \cos(n)+1 ) #

极限推导错误：由于(\sin(n))和(\cos(n))在(n→∞)时持续振荡（取值范围分别为[-1,1]、[-1,1]），(\frac{f(n)}{g(n)})的极限不存在——当(\cos(n) \to -1)时，g(n)→0，比值趋向无穷；当(\cos(n)=1)时，比值在[1,2]之间波动。

用Θ定义判断：g(n)可取到趋近于0的值，而f(n)始终≥2，无法找到正常数(c_1)使得(c_1 \cdot (\cos(n)+1) ≤ \sin(n)+3)对所有足够大的n成立，因此**(f(n)≠Θ(g(n)))**，结论正确但推导过程有误。

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