Сравнительная структура данных для поиска предметов

Существует ли структура данных, которая принимает неупорядоченный массив из элементов, выполняет предварительную обработку в и отвечает на запросы: есть ли какой-то элемент в списке, каждый запрос в наихудшее время ? $n$ $O(n)$ $x$ $O(\log n)$

Я действительно думаю, что нет, поэтому также приветствуется доказательство того, что его нет.

ds.data-structures sorting Chi-Lan
источник

(1) Я не знаю, почему вы можете сказать «Конечно, я рассматриваю ожидаемое время», потому что вы вообще не указываете «ожидаемое» в своем вопросе. Пожалуйста, попробуйте более точно сформулировать свой вопрос, прежде чем сказать «конечно». (2) Пожалуйста, определите «не хасируемый».

Tsuyoshi Ito

(1) Понятно. Спасибо за объяснение. Если бы кто-то спросил: «Тебя волнует время выполнения?», Тогда ответ был бы действительно «конечно». :) (2) Я думаю, что «Единственное разрешенное действие - это сравнение двух значений в списке» гораздо точнее чем просто сказать «не хэшируемый». Можете ли вы отредактировать вопрос так, чтобы людям не приходилось читать комментарии, чтобы понять, что означает «не хэшируемый»?

Цуёси Ито

Кстати, если вы не можете доказать это, почему вы знаете, что это невозможно? Если это упражнение в учебнике или классе, вы спрашиваете на неправильном веб-сайте.

Цуёси Ито

Это ваш вопрос: существует ли структура данных, которая принимает неупорядоченный массив из n элементов, выполняет предварительную обработку в O (n) и отвечает на запросы: есть ли какой-то элемент x в списке, каждый запрос в худшее время O (log n)?

sdcvvc

@Filip: это легко увидеть? Если это правда, то я согласен, что это решает вопрос.

Цуёси Ито

Ответы:

Вот доказательство того, что это невозможно. Предположим, вы можете построить такую структуру данных. Построить это. Затем выберите элементов случайным образом из списка, добавьте к каждому из них, где меньше разницы между любыми двумя элементами в списке, и выполните запросы, чтобы проверить, присутствует ли какой-либо из полученных элементов в списке. список. Вы уже выполнили запросов. $n/\log n$ $\epsilon$ $\epsilon$ $O(n)$

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

Теперь, поскольку элементов, которые вы выбрали, были случайными, ваши сравнения с высокой вероятностью дали достаточно информации, чтобы разделить исходный список на списков, каждый из которых имеет размер . Сортируя каждый из этих списков, вы получаете рандомизированный алгоритм -времени, основанный исключительно на сравнениях, противоречие. $n/\log n$ $n/\log n$ $O(\log n)$ $O(n \log \log n)$

Питер Шор
источник

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

пункты должны быть заполнены пунктами после

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

выполняются; в

списки в «порядке возрастания»: каждый элемент в любом высшем списке выше , чем каждый элемент в любом нижнем списке; после первоначальных запросов у вас будет достаточно информации, чтобы составить списки вокруг элементов, которые вы выбрали случайным образом,

b

$b$

ϵ

$\epsilon$

a \leq b

$a \leq b$

a \geq b

$a \geq b$

n / \log n

$n / \log n$

Алекс тен Бринк

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

Алекс тен Бринк

Я не могу понять это доказательство. Последнее противоречие - это «алгоритм, основанный исключительно на сравнениях», но на первых этапах нашего алгоритма мы добавили

к каждому элементу (далее «где

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

ϵ

$\epsilon$

ϵ

$\epsilon$

Артем Казнатчеев

@Artem: Ваш оригинальный вход состоит из элементов

. Затем вы строите новое множество

; Вы представляете исходный

как

а модифицированный

как

. Теперь вы используете алгоритм черного ящика; алгоритм сравнивает элементы

x \in X

$x \in X$

X^{'} = X \times {0, 1}

$X' = X \times \{0,1\}$

x \in X

$x \in X$

(x, 0) \in X^{'}

$(x,0) \in X'$

x + ϵ

$x + \epsilon$

(x, 1) \in X^{'}

$(x,1) \in X'$

X^{'}

$X'$ друг другу; Чтобы ответить на такие запросы, вам нужно только сравнить постоянное количество элементов

друг с другом. Следовательно, все должно быть выполнимо в модели сравнения с постоянными издержками.

X

$X$

Юкка Суомела

@ Арьябхата: это так. Что такое алгоритм

O (\log^{2} n)

$O(\log^2 n)$

Питер Шор

Я считаю, что здесь есть другое доказательство, доказывающее невозможность временной структуры запроса с предварительной обработкой . $\mathcal{O}(\log ^k n)$ $\mathcal{O}(n)$

Предположим, что в предварительной обработке вы выполняете сравнений, что приводит к частичному порядку. $\mathcal{O}(n)$

Теперь рассмотрим размер самой большой антицепи в этом. Поскольку эти элементы несопоставимы, для того чтобы у нас был алгоритм запроса , мы должны иметь . $A$ $\mathcal{O}(\log ^k n)$ $A = \mathcal{O}(\log ^k n)$

Теперь по теореме Дилворта существует разбиение размера на цепочки. $A$

Теперь мы можем дополнить алгоритм определения цепочек в разделе. Мы можем определить, сопоставимы ли два элемента, создав ориентированный граф сравнений и выполнив анализ достижимости. Это можно сделать без каких-либо дополнительных сравнений. Теперь просто переберите каждый возможный раздел размера чтобы определить, является ли он разделом цепочек. $A$

Получив цепочки, мы можем объединить их, чтобы получить алгоритм сравнений для сортировки всего списка. $\mathcal{O}(n \log \log n)$

Арьябхата
источник

Это хорошая идея. И если бы вы могли показать, что цепочечный раздел должен быть известен алгоритму, то вы могли бы использовать mergesort, чтобы показать, что для сортировки всего ввода потребуется только O (n log log n), а не Дженсен. Но есть проблема: почему алгоритм предварительной обработки должен создавать цепное разбиение? Да, цепное разбиение должно существовать, но это сильно отличается от того, что известно алгоритму.

Дэвид Эппштейн

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

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

O (n \log \log n)

$O(n\log\log n)$

Дэвид Эппштейн

Доказательства на самом деле показывают, что вы должны иметь либо

предварительной обработки, либо

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

Ω (n \log n)

$\Omega(n\log n)$

Ω (n)

$\Omega(n)$

Yuval Filmus

@Yuval: может быть, вы должны записать это наблюдение как фактический ответ, потому что мне кажется, что вы должны сделать умеренный объем работы, чтобы получить вышеуказанный результат из доказательств в ответах.

Питер Шор

@Yuval: думая о доказательствах, я только вижу, что у вас должна быть либо предварительная обработка

либо время запроса

для всех

. Можно иметь

Preprocessing времени и

время запроса. Можно разделить список на

списков размером

каждый за время

Ω (n \log n)

$\Omega(n \log n)$

Ω (n^{1 - ϵ})

$\Omega(n^{1-\epsilon})$

ϵ

$\epsilon$

o (n \log n)

$o(n \log n)$

O (n / \log n)

$O(n / \log n)$

\log n

$\log n$

n / \log n

$n/\log n$

с помощью повторного нахождения медианы.

θ (n \log \log n)

$\theta(n \log\log n)$

Питер Шор

Как отмечается в ответе Питера Шора, чтобы исключить членство в модели, основанной на сравнении, нам нужно знать, как этот элемент сравнивается с каждым членом. Таким образом, используя случайных запросов (число членов меньше, чем запрашиваемое число не является случайным), мы получаем информации относительно наличия несортированных значений. Следовательно, для некоторой константы , используя $k<n$ $Θ(n \log k)$ $n$ $c>0$ предварительной обработки, мы не можем иметь $c \, n \log k$ стоимость запроса. Это оптимально с точностью до постоянного множителя, поскольку мы можем отсортировать данные по приблизительно равным сегментам (каждый сегмент не отсортирован) в время, которое позволяет стоимость запроса. $≤c \, n \log k/k$ $k' = k / \log k ≤ n/\log n$ $O(n \log k') = O(n \log k)$ $O(n/k')$

В частности, используя предварительную обработку, мы не можем иметь стоимость запроса. Кроме того, предварительная обработка соответствует в для каждого и, следовательно, стоимости запроса. $O(n)$ $o(n)$ $o(n \log n)$ $k$ $O(n^ε)$ $ε>0$ $Ω(n^{1−ε})$

Дмитрий Тарановский
источник