如何证明下界 \Omega{(n (logn)^k)} ？ [k>1]
有许多算法在 O(n {log n}^k) 时间内运行，其中 k>1。
如果您能为我提供有关任何问题的一些参考，那将非常有帮助 具有：
\Omega{(n {log n}^k)} 下界，其中 k>1。
我知道 k=1 有很多例子，例如最接近的对/排序。
There are many algorithms run in O(n {log n}^k)-time, where k>1.
It would be very helpful if you could provide me some reference about any problem
that has:
\Omega{(n {log n}^k)} lower bound, where k>1.
I know that there are many examples for k=1, e.g. closest pair/ sorting.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
这是 k=2 的一个人为示例。
您有一个 nxn 数组。数组的每一行都已排序。
每行都具有以下属性：该行中的每个元素（在该行中）出现偶数次，但有一个元素除外，该元素在该行中出现奇数次。
找到每一行的“奇数”元素。
这具有可证明的 Omega(n log^2 n) 下界（并且具有 O(n log^2 n) 算法）。
对于 1 行的情况，我们在这里有证据（在 stackoverflow 上）：如何在 O(n) 时间内找到在排序数组中出现奇数次的数字？ 这证明了 Omega( log^2 n) 下界。它很容易证明这个问题的下界。
Here is a contrived example for k=2.
You have an
nxnarray. Each row of the array is sorted.Each row has the property that every element in the row occurs an even number of times (in that row), except one, which occurs an odd number of times in that row.
Find the "odd" element of each row.
This has provable Omega(n log^2 n) lower bounds (and has O(n log^2 n) algorithms).
For the case of 1 row, we have the proof right here (on stackoverflow) : How can I find a number which occurs an odd number of times in a SORTED array in O(n) time? which proves Omega(log^2 n) lower bounds. It easily proves the lower bound for this problem.