math - 找到一个 O(n^2) 和 Omega(n) 的非递减函数，并且这些边界无法改进

Question

是否有函数 f(可能是实值)使得 f 是

O(n2),

不是 o(n2)，

Ω(n),

不是 ω(n) 和

不减？

(也就是说，f 是 n2 的大 O，不是 n2 的小 o，n 的大欧米茄，不是 n 的小欧米茄，并且非递减)。

Answer 1

本质上，您正在寻找一个函数

有一个紧密的二次上界，

有一个紧密的线性下界，并且

是不减的。

这是执行此操作的一种方法。想象一下绘制曲线 n 和 n2。现在，首先沿着曲线 n2 绘制函数 f 一段时间，然后绘制一条水平线，直到碰到曲线 n 并沿着该曲线追踪一点，然后垂直跳到 n2 并沿着该曲线追踪一点，无限重复这个过程。也就是说，我们正在寻找这样的东西:

这样做的净效果如下:

n2 曲线是 f 上的紧渐近上限。曲线无限常采用 n2 的值并且永远不会超过 n2。这使得 f(n) = O(n2) 但不是 o(n2)。

n 曲线是 f 上的紧渐近下界。曲线无限常采用 n 的值，但永远不会低于 n。这使得 f(n) = Ω(n) 但不是 ω(n)。

函数不减。

这里棘手的部分是为这样的曲线找到一个精确的公式。我们可以使用递归定义来做到这一点。基本思想如下:

每当 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, ...

这是一个有趣的工作 - 希望这会有所帮助!