algorithm - 我怎样才能证明下界是\Omega{(n (logn)^k)} ？ [k>1]

Question

有许多算法在 O(n {log n}^k) 时间内运行，其中 k>1。

如果你能给我一些关于任何问题的引用，那将是非常有帮助的有:

\Omega{(n {log n}^k)} 下界，其中 k>1。

我知道 k=1 的例子有很多，例如最近的对/排序。

Answer 1

这是 k=2 的人为示例。

你有一个 nxn 数组。数组的每一行都已排序。

每一行都有这样的属性，即该行中的每个元素(在该行中)出现偶数次，除了一个元素，它在该行中出现奇数次。

找到每一行的“奇数”元素。

这具有可证明的 Omega(n log^2 n) 下界(并且具有 O(n log^2 n) 算法)。

对于 1 行的情况，我们在这里(在 stackoverflow 上)有证明:How can I find a number which occurs an odd number of times in a SORTED array in O(n) time?这证明了 Omega(log^2 n) 下界。它很容易证明这个问题的下界。