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 上）：如何在 O(n) 时间内找到在 SORTED 数组中出现奇数次的数字？这证明了 Omega(log^2 n) 的下界。它很容易证明这个问题的下界。