Нижние границы для структур данных

14

Известны ли результаты, которые исключают существование «слишком хороших, чтобы быть правдивыми» структур данных?

Например: можно ли добавить функциональность и J o i n в структуру данных ведения заказа (см. Dietz and Sleator STOC '87 ) и при этом получить O ( 1 ) временных операций?SпLяTJояNО(1)

Или: можно ли реализовать упорядоченный набор с целочисленными ключами и временными операциями? Конечно, это по крайней мере так же сложно, как найти алгоритм линейного времени для сортировки целых чисел.О(1)

Было ли доказано, что ответ был отрицательным для любого из этих вопросов? Известны ли результаты нижней границы для любой естественной структуры данных?

Шон Харкер
источник
Все изменится, если мы сможем добавить ограничения в проблемное пространство. Например, если у нас ограниченный набор ключей и достаточно памяти, мы можем отсортировать их по линейному времени, используя битовый вектор.
Jetru
1
Я думаю, что причина того, что вы не получаете слишком много ответов на этот вопрос, заключается в том, что возможностей так много. Многие, многие структуры данных имеют нижние границы, и трудно просто не наткнуться на них. Поиск в Google «структура данных» «нижняя граница» включает в себя 5 статей, которые еще не упомянуты в этой теме. Я думаю, что вы получите больший успех, если получите ответ на свой вопрос, если вы ограничите его, возможно, удалив часть о «естественной структуре данных» и просто спросив о ведении списка или целочисленных упорядоченных наборах (но не оба в одном вопросе).
Jbapple
Я пропустил, что 5 статей, которые я нашел в поиске Google, были только на первой странице результатов поиска.
Jbapple
@jbapple: Вы правы! Я думаю, что клики людей в этом сообществе, пытающихся помочь мне с моим вопросом, подтолкнули хорошие результаты к вершине списка. (Например, ЭТА страница находится в списке!) Я не помню, чтобы она была полезной, когда я впервые выполнил поиск, иначе я бы ограничил вопрос, как вы предлагаете. (Или я был большой куклой, это тоже возможно. :))
Шон Харкер

Ответы:

19

Существует очень приятно говорить о динамических нижних оценках на графиках Михая Pătraşcu. В итоге (на стр. 20 слайдов) у нас есть нижние границы с точки зрения времени запроса и времени обновления t u (вставить ребро):TQTU

введите описание изображения здесь

Смотрите документ для деталей. Некоторые другие работы Михая тоже актуальны и хороши.

ОБНОВЛЕНИЕ: я обнаружил, что его кандидатская диссертация « Методы нижних границ для структур данных » дает нижние оценки для многих проблем центральной структуры данных, используя разработанные им методы. Это, безусловно, стоит прочитать.

Сянь-Чжи Чан 張顯 之
источник
1
Этот тезис замечательный, большое спасибо за то, что поделились ссылкой.
Шон Харкер
6

Ответ на любой из ваших вопросов зависит от модели вычислений. Например, на многих машинах умножение целых чисел обходится дороже, чем их добавление. Некоторые модели отражают это, а некоторые нет.

О(журналN/журналжурналN)

jbapple
источник
Ницца. Но, похоже, вы переоценили результат в работе Андерссона и Торупа. Это относится только к линейным пространственным структурам, а не ко всем полиномиальным пространственным структурам.
Шон Харкер
2
Андерссон и Торуп цитируют Бим и Фич для полиномиального пространства: «Нижняя граница следует из результата Бим и Фич. Это показывает, что даже если мы просто хотим поддержать операции вставки и предшественника в полиномиальном пространстве, одна из этих двух операций имеет наихудшая граница Ω (sqrt (log n / log log n)), совпадающая с нашей общей верхней границей. Отметим, что можно найти лучшие оценки и компромиссы для некоторых отдельных операций. Действительно, мы будем поддерживать min, Максимум, предшественник, преемник, и операции удаления в постоянном времени, и только вставьте и ищите в Θ (sqrt (log n / log log n)) времени. "
Jbapple
Я вижу, линейное пространство входит, чтобы объявить верхнюю границу , но следствие 3.10 Бима и Фича дает нижнюю границу многопространства , как вы заявили, и я глупо противоречил. Мне также приходит в голову, что кто-то может объявить худшие времена для верхних границ, а объявление амортизированных времен для нижних границ. В работе Андерссона и Торупа действительно цитируются (стр. 5) Бим и Фич для амортизированной нижней (и верхней) границы. Но следствие 3.10 только дает нижнюю оценку для наихудшего случая. Может быть, кто-то может дать мне подсказку на это?
Шон Харкер
2

В дополнение к тому, что вы упоминаете в своем вопросе, один классический пример использует тот факт, что целые числа не могут быть отсортированы с использованием сравнений быстрее, чем О(NжурналN) чтобы доказать несуществование надстроек.

Кроме того, весьма обычно использовать аргументы теории информации (например, сложность Колмогорова), чтобы доказать нижние оценки для структур данных.

chazisop
источник