LINUX.ORG.RU
Форум — Development  

Удобная структура данных для множества


0

1

Интересует такой вопрос - а появилась ли в свете бесконечного появления «новых фреймворков, библиотек и технологий» структура данных для хранения не-битовых множеств, удовлетворяющая условиям на трудоемкость:
* проверка на принадлежность элемента - O(1)
* операция объединения множеств с мощностями m и n не более O(m+n)
* операция пересечения множеств с мощностями m и n не более O(m+n)
* кол-во памяти на хранение множества мощности n - не более O(n^2)

>«новых фреймворков, библиотек и технологий»

какое это имеет отношение к развитию компьютерной науки, про которую вопросы?

anonymous
()

Хеш, но все оценки - в среднем. Для худшего случая таких крутых гарантий хеш не даст.

const86 ★★★★★
()
Ответ на: комментарий от const86

Вот тоже минут 5 назад сообразил, что хеш более-менее подходит.

malbolge ★★
() автор топика

А в чем проблема? Реализуйте множество через фибоначиеву пирамиду. Будет даже лучше, объединение и пересечение за O(1), правда оценка в среднем, а не в худшем случае.

anonymous
()
Ответ на: комментарий от anonymous

Ну и хэш тоже, но нормальный хэш еще надо реализовать. Я ведь так понимаю, что ТС именно реализация интересна.

anonymous
()

> * проверка на принадлежность элемента - O(1)

Для множества элементов, про которые ничего не известно? Мило.

sanuda
()

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

Возможно это стоит посмотреть, но оно вероятностное да и как раз для экономии места: http://en.wikipedia.org/wiki/Bloom_filter

ratatosk ★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
Development