Как я могу доказать нижнюю оценку, которая является \ Omega {(n (logn) ^ k)}? [К> 1]

Question

В O (n {log n} ^ k) -времени выполняется много алгоритмов, где k> 1.

Было бы очень полезно, если бы вы могли дать мне ссылку на любую проблему, которая имеет:

\ Omega {(n {log n} ^ k)} нижняя граница, где k> 1.

Я знаю, что есть много примеров для k = 1, например, ближайшая пара / сортировка.

Answer 1

Вот надуманный пример для k = 2.

У вас есть массив nxn.Каждая строка массива сортируется.

Каждая строка обладает свойством, что каждый элемент в строке встречается четное количество раз (в этой строке), кроме одного, что встречается нечетным числом раз в этой строке..

Найдите «нечетный» элемент каждой строки.

Это имеет доказуемую нижнюю границу Омега (n log ^ 2 n) (и имеет O (n log ^ 2 n) алгоритмов).

Для случая 1 строки у нас есть доказательство прямо здесь (на stackoverflow): Как найти число, которое встречается нечетное количество раз в массиве SORTED за O (n) время? что доказывает нижние границы омеги (log ^ 2 n).Это легко доказывает нижнюю оценку этой проблемы.