找到一个非递减函数，它的时间复杂度为O(n^2)和Ω(n)，而且这些上下界是不能被改进的。

Question

是否有一个函数f(可能是实值)，它满足以下条件：

1. 是O(n²),
2. 不是o(n²),
3. 是Ω(n),
4. 不是ω(n), 且
5. 单调不降？

(也就是说，f是n²的大O，不是n²的小o，是n的大Omega，不是n的小omega，并且单调不降)。

- Hagai

---

一个函数符合所有4个标准还是每个标准都有一个函数？ - Armen Tsirunyan

一个函数适用于所有4个标准。 - Hagai

Answer 1

基本上，你正在寻找一种函数，该函数具有以下特征：

1. 具有紧密的二次上界； 2. 具有紧密的线性下界； 3. 是非递减的。

下面是一种实现方式。想象一下绘制出n和n²曲线的图形。现在，通过首先沿着n²曲线行进一段时间，然后绘制一条水平线直到触及n曲线并沿着该曲线行进一段时间，然后垂直跳到n²并沿着该曲线行进一段时间，重复此过程直至无穷远。也就是说，我们要寻找类似于这样的东西：

[图片]

这样做的净效果如下：

1. n²曲线是f的紧密渐近上界。该曲线无限多次地取值为n²，且永远不超过n²。这使得f(n) = O(n²)但不是o(n²)。 2. n曲线是f的紧密渐近下界。该曲线无限多次地取值为n，但永远不会低于n。这使得f(n) = Ω(n)但不是ω(n)。 3. 该函数是非递减的。

这里的棘手之处在于找到这样一个曲线的精确公式。我们可以使用递归定义来做到这一点。基本思想如下：

1. 每当f(n)=n（我们贴着底部曲线），我们将f(n+1)设置为(n+1)²，以便跳到顶部曲线。 2. 每当f(n)>n时，我们将f(n+1)=f(n)。这相当于在触及顶部曲线后水平移动，直到到达底部曲线。

这给出了以下递归定义：

[图片]

这是该函数的前几个值：

0、1、4、4、4、25、25、25、......、25、676、676、...

这是一个很有趣的问题——希望这能帮助你！

- templatetypedef