我有一个算法如下：
甚至我也有找到这个算法下界的答案：
但问题是我不能理解这一点：当我们设置I>=n/2但n/4我真搞不懂为什么。
最佳答案
好吧，我不确定你对哪一部分感到困惑，但让我从你的摘要中重新表述下限解释，也许，困惑的部分会澄清。
首先，下限法（这是很明显的东西，但在你的摘要中被省略了，初学者可能看不到）如果你想象（i，j，k）的所有可能值的集合，我们不想全部计算它们，但我们只计算它们的一个较小的子集，由某些任意限制定义。事实证明，在一个子集上计算下限比在整个集合上更容易（因为由于这些限制，您可以做一些简单的数学运算，比如乘以范围的下限），而且从传递的角度来说，这也是整个集合的下限。
现在，这些任意的限制选择如下：
1）只看i值>=n/2。也就是说，我们不是看[1..n]，而是看[n/2..n]。
2）考虑到之前的限制，也要限制j：查看范围[n/4..n/2]中的j值。文本中的“考虑”一词同时适用于（1）和（2）。注意，我们可以这样做的原因是[n/4..n/2]始终是[1..i]范围的子集，因为我们已经决定只在i>=n/2时查看案例。因此，将[1..i]限制在[n/4..n/2]是获得一些下界的正确方法。
现在我们知道i是[n/2..n]（至少是n/2），j是[n/4..n/2]（至少是n/4），可能的（i，j）对有n/2*n/4个组合。对于这些对中的每一个，内部循环将至少执行N/4-1次迭代（我不确定为什么是-1，可能是为了表示舍入？），因此我们得到（i，j，k）的n/2*n/4*（n/4-1）元组是Ω（n^3）。
如果变量的一小部分是Ω（n^3），那么原始集合也是Ω（n^3）。
我不明白你为什么说“n/4
关于algorithm - 最坏情况下此算法的下限运行时间，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/21010114/