Структура данных как пораженная

Question

Мне нужно предложить такую ​​структуру данных, как Strick, с этими функциями:

1. init() с временной сложностью O (1) : инициализация пустой структуры .
2. push(x) с временной сложностью O (1) : вставить в структуру новый элемент с ключом x .
3. pop() с временной сложностью O (1) : удалить элемент, который был вставлен в структуру последним.
4. getMiddle() с временной сложностью O (1) : вернуть ключ среднего элемента (n / 2) (в порядке вставки).
5. getAt(k) с временной сложностью O (log k) : вернуть ключ элемента k ^th (в порядке вставки).

Сложность пробела O (n) , когда n - номер элементов в структуре.

Мне разрешено использовать следующие структуры: ADT, Queue, Stack, Array, Linked List, Binary Tree и Дерево двоичного поиска.

Я подумал, что бой с использованием связанного списка, потому что инициализация списка O (1) . Чтобы вставить элемент и удалить элемент также O (1) . В функциях push и pop я подумал использовать указатель, указывающий на середину, и при каждой вставке или удалении указатель будет перемещаться. Итак, в функции middle верните ключ по этому указателю.

Моя проблема - последняя программа. Я думал о выполнении двоичного поиска, но временная сложность составляет O (log (n)) , и мне нужно O (log (k)) . Я думал разделить список на элемент k ^th , но не знаю как.

Есть ли у вас какие-либо предложения по решению этой проблемы?

Answer 1

Интересная проблема!

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

Если вам нужно выполнить все эти требования в смысле наихудшего , единственный вариант данных, который я могу придумать, который соответствует ограничениям, - это расширяемый массив структура данных, которая, по сути, является деамортизированной версией массива c Dynami. Его можно построить из двух массивов, но предполагается, что вы можете выделить блок памяти размером n за время O (1).

Я думал над другими вариантами, чтобы посмотреть, есть ли что-то попроще, но ничего из того, что я пробовал, не получается. Например, skiplist позволяет вам получить (ожидаемый случай) O (log k) поиск k-го элемента. Для этого начните с нижнего слоя и двигайтесь вверх, пока не дойдете до элемента, который находится за k-й позицией, затем выполните обычный поиск skiplist, начиная с этого уровня или ниже. Идея состоит в том, что в среднем при первом превышении позиции k вы будете в позиции примерно 2k, и поиск в этом субскиплисте займет время O (log 2k) = O (log k), чтобы найти то, что вы ищете.

У такого подхода есть две проблемы. Во-первых, скиплисты рандомизируются, хотя это можно преодолеть, используя детерминированную c версию скиплиста (они существуют, хотя и не так широко известны). Во-вторых, стоимость вставки в skiplist не равна O (1) из-за затрат на подключение соответствующих указателей. Вы можете показать, что амортизированная стоимость вставки в такой скиплист будет O (1), если вы используете детерминированную схему c, но если вы стремитесь к амортизированной эффективности, вы должны просто использовать динамический c array.

Другой вариант, который я рассматривал, был чем-то вроде VList - связанного списка блоков элементов, размеры которых экспоненциально растут по мере продвижения вперед. Затем поиск k-го элемента может быть выполнен за время O (log k), просто пройдя вперед по связанному списку, пока не найдете блок подходящего размера, а затем загляните в этот блок. Количество блоков, которые вы посетите таким образом, равно O (log k), потому что после посещения i блоков вы пройдете более 2 ^{i + 1} - 1 элементов. Проблема здесь в том, что это предполагает, что вы можете выделить блок памяти за время O (1), и если это так, вы можете просто использовать расширяемый массив, упомянутый ранее.

Если я думаю о чем-то еще , Я обязательно обновлю этот ответ. Интересно, не хватает ли мне какой-нибудь более простой стратегии?