算法O、Ω、Θ界疑问：f(n)=log(n+5)与g(n)=log(25n²)的关系

一、log(2n)的由来解释 #

当n>5时，显然n+5 < n + n = 2n（因为n>5时，n本身大于5，加n肯定比加5大）。而对数函数（底数>1时）是单调递增的，对不等式两边取对数后方向不变，因此得到：
log(n+5) < log(2n)
注意这里是对数包裹2n，不是线性函数2n，别混淆两者。

二、完整渐近关系推导 #

先利用对数运算法则化简g(n)：
g(n) = log(25n²) = log25 + log(n²) = log25 + 2logn

1. 证明f(n) = O(g(n)) #

O记号的核心是：存在常数C>0和n₀>0，当n≥n₀时，f(n) ≤ C·g(n)。

• 当n>5时，f(n)=log(n+5) < log(2n) = log2 + logn
• 当n≥25时，logn ≥ log25，此时：
  log2 + logn ≤ logn + logn = 2logn ≤ 2logn + log25 = g(n)
  取C=1，n₀=25，满足f(n) ≤ g(n)，因此f(n)是g(n)的O。

2. 证明f(n) = Ω(g(n)) #

Ω记号的核心是：存在常数C>0和n₀>0，当n≥n₀时，f(n) ≥ C·g(n)。

• 当n>5时，f(n)=log(n+5) > logn
• 当n≥25时，logn ≥ log25，所以g(n)=log25 + 2logn ≤ logn + 2logn = 3logn < 3f(n)
  整理得f(n) ≥ (1/3)g(n)，取C=1/3，n₀=25，满足条件，因此f(n)是g(n)的Ω。

3. 判定是否为Θ、o、ω #

• Θ记号要求f(n)同时满足O(g(n))和Ω(g(n))，上面已证明，因此f(n)是g(n)的Θ。
• o记号要求lim(n→∞) f(n)/g(n) = 0，计算极限：
  lim(n→∞) log(n+5)/(log25 + 2logn) = lim [logn + log(1+5/n)]/[2logn + log25]
  分子分母同除以logn，得lim [1 + (log(1+5/n)/logn)]/[2 + (log25/logn)] = 1/2（非0常数），因此不是o。
• ω记号要求lim(n→∞) f(n)/g(n) = ∞，显然极限为1/2，不满足，因此不是ω。

结论 #

f(n)是g(n)的O、Ω、Θ，不属于o和ω。

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