Вопросы с тегом «ds.data-structures»

15
Известные примеры идеи квадратного корня в анализе сложности

k = √max { k , n / k }max{k,n/k}\max \left\{k, n/k\right\}k = n--√k=nk=\sqrt n алгоритм гигантского шага baby-step для вычисления дискретного логарифма в O ( n--√)O(n)O(\sqrt n) , статический двухмерный ортогональный отсчет во времени O ( n--√)O(n)O(\sqrt n) и памяти O ( n )O(n)O(n) , приоритетная...

15
Что такое молния и как она связана с древовидной структурой?

Я читал главу в LYAH, которая не имела для меня никакого смысла. Я понимаю, что молнии могут произвольно пересекать древовидную структуру, но мне нужно кое-что прояснить. Кроме того, могут ли молнии быть обобщены на любую структуру...

15
Экспоненциальное ускорение во внешней памяти

Фон Внешняя память, или модель DAM, определяет стоимость алгоритма по количеству операций ввода-вывода, которые он выполняет (по сути, по числу пропущенных кешей). Эти времена выполнения обычно даются в терминах , размера памяти и B , количества слов, которые могут быть переданы в память за один...

14
Нужен хороший обзор для алгоритмов сжатой структуры данных

(уже просили на главном сайте , но просим также о лучшем освещении, извините) Так как я знал о сжатых структурах данных, мне отчаянно нужен хороший обзор последних событий в этой области. Я погуглил и прочитал много статей, которые я мог видеть в верхней части результатов Google по запросам сверху...

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

Известны ли результаты, которые исключают существование «слишком хороших, чтобы быть правдивыми» структур данных? Например: можно ли добавить функциональность и J o i n в структуру данных ведения заказа (см. Dietz and Sleator STOC '87 ) и при этом получить O ( 1 ) временных операций?Sp l i...

14
Повторное использование 5-независимых хеш-функций для линейного зондирования

В хеш-таблицах, которые разрешают коллизии линейным зондированием, для обеспечения ожидаемой производительности необходимо и достаточно, чтобы хеш-функция была из 5-независимого семейства. (Достаточность: «Линейное зондирование с постоянной независимостью», Паг и др. , Необходимость: «О...

14
Чисто функциональный эквивалент B-Tree?

Я изучаю идею написания СУБД чисто функциональным способом. Традиционной структурой данных, используемой для индексации, является B-Tree. Я хотел бы знать какой-то чисто функциональный эквивалент B-Tree, который был бы оптимизирован для минимизации доступа к диску....

14
Ассоциативное смешивание хешей

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

14
Поддиапазон красного и черного дерева

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

13
Сколько независимости требуется для отдельного сцепления?

Если шаров равномерно размещены в n корзинах случайным образом, то в самой тяжелой загруженной корзине с высокой вероятностью будет O ( lg n / lg lg n ) шариков. В «Сложности простого хэширования табуляции» Патрашку и Торуп упоминают, что «границы Черноффа-Хёффдинга для приложений с ограниченной...

13
Списки различий в функциональном программировании

Вопрос Что нового в чисто функциональных структурах данных со времен Окасаки? и эпический ответ jbapple, упомянутый с использованием списков различий в функциональном программировании (в отличие от логического программирования), что меня недавно интересовало. Это привело меня к поиску реализации...

13
Ссылка на фундаментальную теорему о вращениях деревьев

Два бинарных дерева поиска называются линейно эквивалентными, когда они сходятся в своих обходах по порядку. Следующая теорема объясняет, почему повороты деревьев так фундаментальны: Пусть A и B - бинарные деревья поиска. Тогда A и B линейно эквивалентны тогда и только тогда, когда они связаны...

13
Структура данных для обновления интервалов и запроса количества нулей

Я ищу структуру данных, которая бы поддерживала целочисленную таблицу ttt размера и позволяла бы выполнять следующие операции за время .nnnO(logn)O(log⁡n)O(\log n) increase(a,b)increase(a,b)\text{increase}(a,b) , которое увеличивает .t[a],t[a+1],…,t[b]t[a],t[a+1],…,t[b]t[a],t[a+1],\ldots,t[b]...

12
Простые сбалансированные деревья с O (1) concat?

В чисто функциональном худшем случае отсортированные списки с возможностью прокрутки по постоянному времени, Brodal et al. представить чисто функциональные сбалансированные деревья с O (1) сцеплением и O (lg n) вставкой, удалением и поиском. Структура данных несколько сложна. Существует ли более...

12
Целочисленная приоритетная очередь с чувствительным к распределению deleteMin

Есть ли в очереди с целочисленным приоритетом, которая использует слов пробела со следующими операциями, все в наихудшем времени и без доступа к случайности:O(n)O(n)O(n) createEmptyQueueв для некоторой константы с .O(lgcU)O(lgcU)O(lg^c U)ccc insertв .O(1)O(1)O(1) deleteMinδ...

12
Вычисление приблизительной популяции фильтра Блума

Дан фильтр Блума размером N битов и K хэш-функций, из которых установлены M-биты (где M <= N) фильтра. Можно ли приблизить количество элементов, вставленных в фильтр Блума? Простой пример Я обдумывал следующий пример, предполагая, что BF состоит из 100 битов и 5 хэш-функций, где установлены 10...

12
Сторнирование списка с использованием двух очередей

Этот вопрос основан на существующем вопросе о том, можно ли моделировать стек с использованием двух очередей с амортизированным раз на операцию стека. Ответ кажется неизвестным. Вот более конкретный вопрос, соответствующий особому случаю, когда сначала выполняются все операции PUSH, а затем все...

12
Структура данных для динамического распределения памяти

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

12
Минимальные элементы монотонного предиката над набором мощности

Рассмотрим монотонный предикат над множеством степеней (упорядоченный по включению). Под «монотонным» я подразумеваю: такой, что , если то . Я ищу алгоритм, чтобы найти все минимальные элементы , то есть такие, что но , . Поскольку ширина равна n \, выберите n / 22 | п | ∀ x , y ∈ 2 | п | x ⊂ y P (...

11
Найти наименьшее попарное расстояние между точками в o (n log n)?

Следующие упражнения были розданы студентам, которых я курирую: Учитывая точек на плоскости, разработайте алгоритм, который находит пару точек, расстояние которых минимально среди всех пар точек. Алгоритм должен работать за время o ( n 2 ) .nnno(n2)o(n2)o(n^2) Существует (относительно) простой...