关于大O符号的函数求解问询：介于对数与多项式之间

架构老林

2026-5-20

满足条件的函数示例与解释

刚好这个问题是算法复杂度分析里经典的「介于多项式和对数多项式之间的渐近函数」问题，我给你举几个直观的例子，再拆解为什么它们符合要求：

最常用的例子：f(n) = e^{\sqrt{\log n}}（也就是exp( sqrt(log n) )）
我们分两个核心条件验证：
1. 对任意固定的k，(log n)^k = O(f(n))：
  当n趋向于无穷大时，指数函数e^{\sqrt{\log n}}的增长速度比对数的任意次多项式都快。你可以取对数对比：log((log n)^k) = k log log n，而log(f(n)) = sqrt(log n)。显然sqrt(log n)比k log log n增长得更快（比如令t=log n，当t→∞时，sqrt(t)/log t →∞），所以(log n)^k与f(n)的比值会趋向于0，满足大O条件。
2. 对任意ε>0，f(n) = O(n^ε)：
  同样取对数分析：log(n^ε) = ε log n，而log(f(n)) = sqrt(log n)。当n足够大时，ε log n远大于sqrt(log n)（令t=log n，εt/sqrt(t) = ε sqrt(t) →∞），所以f(n)/n^ε的比值趋向于0，符合大O要求。
另一个等价的直观形式：f(n) = n^{1 / \log \log n}
这个形式看起来更接近多项式，但指数是随n变化的：
1. 验证(log n)^k = O(f(n))：
  取对数得log(f(n)) = (log n)/log log n，而log((log n)^k) = k log log n。当n→∞时，(log n)/log log n除以k log log n等于log n / (k (log log n)^2)，这个值趋向于无穷大，说明f(n)的增长速度比(log n)^k快。
2. 验证f(n) = O(n^ε)：
  取对数后计算差值：log(f(n)) - log(n^ε) = (log n)/log log n - ε log n = log n (1/log log n - ε)。当n足够大时，log log n会超过1/ε，此时括号内的项为负，整个式子趋向于负无穷，所以f(n)/n^ε趋向于0，满足条件。