是否有一个函数f(可能是实值),它满足以下条件: 是O(n2), 不是o(n2), 是Ω(n), 不是ω(n), 且 单调不降? (也就是说,f是n2的大O,不是n2的小o,是n的大Omega,不是n的小omega,并且单调不降)。
基本上,你正在寻找一种函数,该函数具有以下特征:1. 具有紧密的二次上界; 2. 具有紧密的线性下界; 3. 是非递减的。下面是一种实现方式。想象一下绘制出n和n2曲线的图形。现在,通过首先沿着n2曲线行进一段时间,然后绘制一条水平线直到触及n曲线并沿着该曲线行进一段时间,然后垂直跳到n2并沿着该曲线行进一段时间,重复此过程直至无穷远。也就是说,我们要寻找类似于这样的东西:[图片]这样做的净效果如下:1. n2曲线是f的紧密渐近上界。该曲线无限多次地取值为n2,且永远不超过n2。这使得f(n) = O(n2)但不是o(n2)。 2. n曲线是f的紧密渐近下界。该曲线无限多次地取值为n,但永远不会低于n。这使得f(n) = Ω(n)但不是ω(n)。 3. 该函数是非递减的。这里的棘手之处在于找到这样一个曲线的精确公式。我们可以使用递归定义来做到这一点。基本思想如下:1. 每当f(n)=n(我们贴着底部曲线),我们将f(n+1)设置为(n+1)2,以便跳到顶部曲线。 2. 每当f(n)>n时,我们将f(n+1)=f(n)。这相当于在触及顶部曲线后水平移动,直到到达底部曲线。这给出了以下递归定义:[图片]这是该函数的前几个值:0、1、4、4、4、25、25、25、......、25、676、676、...这是一个很有趣的问题——希望这能帮助你!