求满足O(n²)但非Ω(n²)、Ω(n)但非O(n)的渐近函数示例及方法

最经典的例子是f(n) = n log n，我们逐个验证它满足所有条件：

• 属于O(n²)：当n≥2时，log n ≤ n，所以n log n ≤ n * n = n²，取常数c=1、n₀=2就能满足O(n²)的定义。
• 不属于Ω(n²)：假设存在常数c>0，使得对所有足够大的n，n log n ≥ c n²，化简得log n ≥ c n。但对数函数的增长速度远慢于线性函数，当n足够大时这个不等式必然不成立，因此f(n)不属于Ω(n²)。
• 属于Ω(n)：当n≥2时，log n ≥1，所以n log n ≥ 1 * n，取c=1、n₀=2即可满足Ω(n)的定义。
• 不属于O(n)：假设存在常数c>0，使得对所有足够大的n，n log n ≤ c n，化简得log n ≤ c。但当n>e^c时，log n会超过c，矛盾，因此f(n)不属于O(n)。

另外还有很多同类例子：

• 幂函数类：f(n) = n^1.5（也就是n * sqrt(n)），指数k满足1<k<2的幂函数都符合，比如n^1.2、n^1.8等。
• 混合类：f(n) = n² / log n，这个函数增长比n快（n²/log n /n = n/log n → ∞），比n²慢（n²/log n /n² = 1/log n →0）。

核心思路是找一个函数，满足两个极限条件：

1. lim(n→∞) f(n)/n = ∞：这保证了f(n)增长比n快，因此不属于O(n)，同时满足Ω(n)的要求（因为f(n)最终会远大于n）。
2. lim(n→∞) f(n)/n² = 0：这保证了f(n)增长比n²慢，因此不属于Ω(n²)，同时满足O(n²)的要求（因为f(n)最终会远小于n²）。

基于这个思路，你可以快速构造出符合要求的函数：

• 幂函数法：取指数在(1,2)之间的幂函数，比如n^k（1<k<2），因为n^k /n =n^(k-1)→∞（k-1>0），n^k/n² =n^(k-2)→0（k-2<0）。
• 乘积法：用n乘以一个递增且趋于无穷，但增长速度慢于n的函数，比如log n、log log n、sqrt(n)等。比如n*log log n也符合条件——n*log log n /n =log log n→∞，n*log log n /n²= log log n /n→0。

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