Как доказать нижнюю границу logn для структуры данных?

Question

У меня следующий домашний вопрос (обратите внимание, что я не ищу точных ответов, просто ищу простые предложения для продолжения).

S - это структура данных, которая поддерживает Insert (x, S), Delete (x, S) и Find_Smallest_Item (S) во времени <= T (n). Докажите нижнюю оценку для T (n) например, Ω (logn). </p>

Вот мои мысли на данный момент:

Полагаю, мне нужно найти сокращение, где я уменьшу эту проблему до более простой и докажу, что она не может быть ниже logn. Я прочитал много уроков о нижних границах, и большинство из них уменьшило проблему до сортировки, затем они использовали сортировку как черный ящик и доказали, что алгоритм не может быть ниже, чем nlogn.

Но здесь мы имеем дело с logn, и я не знаю такого алгоритма, к которому можно было бы привести. Может, нужно что-то сделать с глубиной древовидной структуры, логн. Но я не мог понять, с чего начать.

Можете ли вы предложить мне несколько советов?

Редактировать : На самом деле что-то пришло мне в голову, но я не знаю, должен ли я доказать нижнюю границу с помощью такого трюка. Итак, я предполагаю, что у меня есть операции вставки, удаления и find_smallest, каждая из которых имеет сложность времени входа в систему.

Например, для построения отсортированного списка я могу использовать функции delete и find_smallest, например, Я могу запустить find_smallest в первый раз, и после нахождения наименьшего элемента в списке, я удалю элемент. Я буду запускать его еще раз, и поэтому я найду 2-й самый маленький элемент и так далее.

Поэтому я могу реализовать сортировку, используя функции delete и find_smallest. Поэтому, если я продолжу делать это n раз, каждому из них потребуется logn (для удаления) + logn (для поиска наименьшего), поэтому в целом сортировка займет nlogn.

Я не знаю, как настроить это для вставки.

Редактировать 2: Чтобы использовать вставку для доказательства: после нахождения i-го наименьшего элемента в списке, что если я вставлю его в i-е место? например после нахождения 3-го наименьшего элемента с помощью описанной выше процедуры я могу вставить его в 3-й индекс структуры данных. Поэтому в конце я получу отсортированную структуру данных.

Answer 1

Если свести вашу проблему к другой, вы получите верхнюю оценку вашего O (), а не нижнюю.

С другой стороны, если вы можете использовать любое решение вашей проблемы для реализации какого-либо другого алгоритма с хорошо известной нижней границей (эффективно сводящей эту проблему к вашей), это может дать вам нижнюю оценку, которую вы ищете .

---

Ответ:

Как предлагали другие, вы можете использовать структуру данных S для осуществления сортировки:

for i in range(input):
    Insert(S, input[i])
for i in range(input):
    x = Find_Smallest_Item(S)
    output[i] = x
    Delete(S, x)

Для ввода размера N этот алгоритм делает N вызовов для каждой из трех ваших операций. Однако мы знаем, что любой алгоритм сортировки общего назначения должен иметь наихудший случай O (N log N).

Это означает, что будут случаи, для которых среднее время вызовов структуры данных в вышеупомянутой сортировке равно O (log N) на вызов. Поскольку это несовместимо с любым T (), асимптотически лучше, чем log N, у вас есть нижняя граница.

Некоторые заметки:

• Тип структуры данных, описанный в вашей проблеме, называется приоритетной очередью .

• Поскольку вы пытаетесь доказать нижнюю границу любой возможной очереди приоритетов, вы не можете сделать предположение о реализации. То, что конкретная структура данных дает вам определенную производительность O (), не означает, что какая-то совершенно другая структура данных не может быть лучше.

• Существует много структур данных очереди с приоритетами, которые удовлетворяют O (log N) для всех вызовов, так что на самом деле это жесткая нижняя граница.

Answer 2

Я думаю, что вы получили ответ довольно близко. Если вы хотите доказать нижнюю границу операций S с помощью сортировки, вы просто реализуете алгоритм сортировки:

sort_with_S(items)
  S s
  add all items to s .............. < n*T_insert
  while s nonempty
    output find_smallest .......... < n*T_find_smallest
    remove the smallest element ... < n*T_remove

Теперь вы суммируете время для операций. Если ваш алгоритм (и, следовательно, ваша структура) может обрабатывать любой тип элемента, который можно сравнить, вы знаете, что алгоритм сортировки имеет наихудшую сложность Omega(n log n). Вы предполагаете (в постановке задачи), что все три операции имеют сложность <= T (n), это означает, что ваш S может сортировать со сложностью <code>O(n T(n)). Вы просто сравниваете границы ...

Answer 3

Ваше первое редактирование неверно.

Я могу запустить find_smallest в первый раз, и после нахождения наименьшего элемента в списке ,

Запуск Find_Smallest_Item(S) найдетсамый маленький элемент в S , а не самый маленький элемент в списке .Сначала нужно вставить (элементы из списка, S), прежде чем есть что найти!

Может быть, вам следует попытаться записать некоторый код, например:

List l = [1,25,4,3,7]
S S         // empty
List sorted // empty
//now we can do:
insert(l[0],S)
//or
delete(25,S)
//magic goes here
...
//and l is sorted!

Хитростьэто записать код, который сортирует l (или создает другой отсортированный список).Чтобы доказать нижнюю границу, посчитайте шаги (вставки, удаления и findmins) и используйте тот факт, что независимо от того, какой код вы пишете, он не может быть (в худшем случае) быстрее, чем O(nlogn) (для сравнительных сортировок).Это дает нижнюю границу, она должна быть не ниже slow .

Answer 4

Сортировка на основе сравнения - это Ω (n * log (n)), поскольку проблему можно сформулировать как проблему дерева решений, где на каждом внутреннем узле вы сравниваете 2 элемента списка.Алгоритм должен быть в состоянии достичь любой перестановки входных данных, и, таким образом, число листов в дереве решений должно быть не менее n !.Число листьев в бинарном дереве не более 2 ^ h, где h - высота, поэтому n!<= 2 ^ ч.Отсюда h> = log_2 (n!), Что равно Ω (n * log (n)).

Указанные вами операции не должны учитывать все n!перестановки ввода, только O (n), как упомянуто SpeedBirdNine.Используйте это, чтобы ограничить высоту дерева решений, ведущего к листу.

Answer 5

Ω(logn) является примером нижней границы, вас просят доказать, что T(n) имеет нижнюю границу, а не то, что ее нижняя граница равна Ω(logn)

Answer 6

Ну, это довольно широкий вопрос, нижняя граница для Insert (x, S), Delete (x, S) и Find_Smallest_Item (S) будет зависеть от того, какая структура данных используется для хранения элементов, в которых она находится. будучи вставленным и т. д., как для массива, который вы можете вставить в O (1), удаление зависит от нахождения элемента в этом массиве и последующего его удаления (с помощью линейного поиска это будет O (n), а с помощью бинарного поиска это будет O (log n)), а для Find_Smallest_Item для массива речь идет о сортировке, если данные случайные, это будет O (n), но вы можете использовать трюк, например переменную, чтобы сохранить наименьшее, и при вставке сравните его с тем, что это наименьшее, и если это не так, измените наименьшее, затем вы можете вернуть это наименьшее в O (1), и если вам нужен указатель и т. д., где точно находится этот наименьший элемент, вы можете найти его в O (log п).

С деревом это совсем другая история.

Итак, какая структура данных S имеет большое значение, но здесь вам нужна нижняя граница, т. Е. Насколько низкой может быть нижняя граница, для этого вам нужно посмотреть, как вы докажете, что независимо от того, что сделано, вставьте не может иметь эту нижнюю границу, delete имеет эту нижнюю границу, а find_smallest имеет эту нижнюю границу. Это означает, что вам нужно предоставить нижнюю границу для всех методов, все, что возможно.

Это интересная проблема, и опубликуйте свои выводы здесь. Просто для интереса сортировка из бисера теоретически может сортировать по O (1).