algorithm - \Omega{(n (logn)^k)} である下限を証明するにはどうすればよいですか? [k>1]

Question

O(n {log n}^k)-time (k>1) で実行される多くのアルゴリズムがあります。

次のような問題について参考にしていただけると助かります。

\Omega{(n {log n}^k)} 下限、ここで k>1。

k=1 には多くの例があることを知っています。たとえば、最も近いペア/並べ替えです。

Answer 1

これは、k=2 の場合の不自然な例です。

nxn配列があります。配列の各行がソートされます。

各行には、その行で奇数回発生する 1 つを除いて、行内のすべての要素が (その行で) 偶数回発生するというプロパティがあります。

各行の「奇数」要素を見つけます。

これには証明可能な Omega(n log^2 n) 下限があります (そして O(n log^2 n) アルゴリズムがあります)。

1 行の場合、ここ (stackoverflow) に証明があります: O(n) 時間で SORTED 配列で奇数回発生する数値を見つけるにはどうすればよいですか? これは Omega(log^2 n) の下限を証明します。この問題の下限は簡単に証明できます。