сложность мультимножества, карты и хеш-карты

Я хотел бы знать сложность нотации Big O классов мультимножества STL, карт и хэш-карт, когда:

  • вставка записей
  • доступ к записям
  • получение записей
  • сравнение записей

c++ big-o complexity-theory
person Community    schedule 21.10.2008    source источник
comment
на самом деле это мой пост, и я не могу понять, почему я кажусь неактивным и, следовательно, не могу его изменить...   -  person Harry    schedule 25.07.2009

Ответы (1)


arrow_upward
111
arrow_downward

карта, набор, мультикарта и мультимножество

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

Вставка: O(log n)
Поиск: O(log n)
Удаление: O(log n)

hash_map, hash_set, hash_multimap и hash_multiset

Они реализованы с помощью хеш-таблиц. Они имеют следующие сроки выполнения:

Вставка: O(1) ожидается, O(n) в худшем случае
Поиск: O(1) ожидается, O(n) в худшем случае
Удаление: O(1) ожидается, O(n) в худшем случае

Если вы используете правильную хэш-функцию, вы почти никогда не увидите поведение в худшем случае, но об этом следует помнить — см. Отказ в обслуживании с помощью атак алгоритмической сложности Кросби и Уоллаха в качестве примера.

person Adam Rosenfield    schedule 21.10.2008
comment
Все, что вы говорите в hash_*, относится к неупорядоченным контейнерам С++ 11 и контейнерам Boost.Unordered? - person myWallJSON; 11.12.2011
comment
Шаблоны классов hash_* являются частью Silicon Graphics STL. Они были включены в версию C++11 под именами unordered_* (unordered_map, unordered_set и т. д.). Кроме того, они были включены в библиотеки libstdc++, Visual C++ и Boost C++. - person milpita; 20.09.2016
comment
@CEOatApartico: исправлена ​​неработающая ссылка - person Adam Rosenfield; 29.11.2018
comment
Я не понимаю ожидаемого O и наихудшего случая O. Big-O по определению является наихудшим случаем. - person Paulius Liekis; 02.01.2021
comment
@PauliusLiekis Вы не знаете, о чем говорите. Big-O по определению является верхней границей, которая не имеет ничего общего с наихудшим случаем, avg. случае, в лучшем случае. - person ypnos; 03.01.2021
comment
Чтобы объяснить это: нотация Ландау описывает рост функции. Если вы различаете случаи, как в хэш-карте, вы имеете дело с разными функциями сложности, и у каждой из них есть свой рост и ограничение. - person ypnos; 03.01.2021
comment
@ypnos да, признаюсь - не понимаю. Меня это на самом деле беспокоит :) Но я тоже не понимаю вашего объяснения :/ позвольте перефразировать вопрос: допустим, у нас есть std::hash_map‹std::string, T› — я могу построить такой объект, где все ключи будут жить в одном сегменте, поэтому поиск записей займет O(N) или O(log N) в зависимости от реализации. Так как же можно утверждать, что поиск записей — это O(1)? Я честно хочу понять. - person Paulius Liekis; 03.01.2021
comment
Я вижу обоснование в этом. Имея хеш-карту с соответствующей хеш-функцией и размером, вы ожидаете, что размер корзины не будет расти с увеличением n, и вы получите в среднем O(1). Ответственность за выбор подходящей хеш-функции лежит на разработчике. Чтобы гарантировать соответствующий размер (коэффициент загрузки), повторное хеширование может запускаться при вставке, и мы получаем наихудший случай O (n) + O (1) = O (n). Символы Ландау не охватывают такого различия между двумя разными алгоритмами! Итак, все, что вам осталось, это указать две разные меры для среднего и наихудшего случая, и обе могут использовать O(), o(), Ө() и т. д. - person ypnos; 05.01.2021