有许多算法在o（n{logn}^k）时间内运行，其中k>1。
如果你能给我提供一些有关任何问题的参考资料，那将是非常有帮助的
有：
\ω{（n{logn}^k）}下界，其中k>1。
我知道k=1有很多例子，例如最近的对/排序。
最佳答案
这里有一个k=2的人为例子。
你有一个nxn数组。数组的每一行都被排序。
每一行都具有这样的属性：行中的每个元素出现偶数次（在该行中），只有一个元素在该行中出现奇数次。
找到每行的“odd”元素。
这有可证明的Ω（n log^2n）下界（并且有O（n log^2n）算法）。
对于一行的情况，这里有证明（在stackoverflow上）：How can I find a number which occurs an odd number of times in a SORTED array in O(n) time?这证明了omega（log^2n）下界。它很容易证明这个问题的下限。
关于algorithm - 如何证明\Omega {(n(logn)^ k)}的下限？ [k> 1]，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/4923660/