\ Omega {（n（logn）^ k）}という下限をどのように証明できますか？ [k> 1]

Question

O（n {log n}^k）時間で実行される多くのアルゴリズムがあります。ここで、k> 1です。あなたは私の持っているすべての問題 に関するいくつかのリファレンスを提供することができれば

それは非常に参考になる：オメガ\

を{（nは{ログのn}^k）を}、下限ただし、k> 1。例えば、k = 1の例が多数あることがわかる。最も近いペア/ソート。

Answer 1

ここでは、k = 2のための人為的な例です。

あなたはnxnの配列を持っています。配列の各行がソートされます。

各行には、その行のすべての要素が（その行内で）偶数回発生するというプロパティがあります。ただし、その行では奇数回発生します。

各行の「奇数」要素を探します。

これは、オメガ（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）の下限を証明しています。この問題の下限を容易に証明します。