求不存在Θ（theta）界的非平凡时间函数T(n)示例

这个问题问得好！确实存在这种非平凡的函数——它们的核心特点是增长速度没有稳定的“节奏”，会在不同量级之间无规律跳变，导致没法用一个简洁的、非平凡的函数g(n)（排除T(n)本身或其线性变换这类情况）来同时作为它的渐近上界和下界。

下面给两个经典的例子：

示例1：交替跳变的分段函数 #

我们定义这样一个函数：

当 n 是 2 的幂时，T(n) = n²；
当 n 不是 2 的幂时，T(n) = n。

来拆解一下为什么它没有非平凡的Θ界：

• 先看渐近上界：显然T(n) ∈ O(n²)，因为不管n是不是2的幂，T(n)都不会超过n²（n≥2时，n≤n²）；
• 再看渐近下界：T(n) ∈ Ω(n)，因为所有情况下T(n)都不小于n；
• 但你找不到任何非平凡的g(n)满足T(n) ∈ Θ(g(n))：
  • 要是选g(n)=n，那当n是2的幂时，T(n)=n²会远大于任意常数c乘以n（只要n>c，n²>c·n），不符合Θ的下界要求；
  • 要是选g(n)=n²，那当n不是2的幂时，T(n)=n会远小于任意常数c乘以n²（只要n>1/c，n < c·n²），不符合Θ的上界要求；
  • 哪怕选中间的g(n)比如n^{1.5，同样不行：当n是2的幂时n²远超c·n}1.5，当n不是2的幂时n又远小于c·n^1.5，永远没法用固定的常数区间把T(n)/g(n)框住。

示例2：带无限振荡的函数 #

再给一个更平滑的例子，用三角函数制造无限振荡的增长速度：

T(n) = n^((1 + sin(n))/2)

这里sin(n)作为整数n的函数，会在[-1,1]之间无限次振荡（因为π是无理数，整数n永远不会正好落在sin的极值点上，但会无限接近）。这导致T(n)的增长速度一直在变化：

• 当sin(n)趋近于1时，T(n)≈n；
• 当sin(n)趋近于-1时，T(n)≈1；
• 当sin(n)=0时，T(n)=√n；
  同样的，它的渐近上界是O(n)，下界是Ω(1)，但找不到非平凡的g(n)满足Θ(g(n))：选g(n)=√n的话，遇到T(n)=n的情况会超界；选g(n)=n的话，遇到T(n)=1的情况又会远低于下界，任何中间函数都没法覆盖所有振荡场景。

本质原因 #

Θ(g(n))的核心要求是：当n足够大时，T(n)和g(n)的比值必须落在一个固定的常数区间[c₁,c₂]里，不会跑出这个范围。而上面的例子中，函数的增长速度会无限次在不同量级之间跳变，导致这个比值要么无限增大，要么无限减小，永远没法被固定的常数区间框住——这就是它们不存在非平凡Θ界的根本原因。

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