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

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

  • вставка записей
  • доступ к записям
  • получение записей
  • сравнение записей
68
задан gsamaras 23 April 2016 в 17:20
поделиться

2 ответа

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

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

Вставка: O (регистрируют n)
Поиск: O (регистрируют n)
Удаление: O (регистрируют n)

hash_map, hash_set, hash_multimap, и hash_multiset

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

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

при использовании надлежащей хеш-функции Вы никогда не будете почти видеть худшего поведения случая, но это - что-то, чтобы иметь в виду, что — видят Отказ в обслуживании через Алгоритмические Нападения Сложности Crosby и Wallach для примера этого.

100
ответ дан Adam Rosenfield 24 November 2019 в 14:18
поделиться

Можно найти эту информацию в документации STL SGI: http://www.sgi.com/tech/stl/

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

, Очевидно, большим преимуществом Hashmap является O (1) для вставки и нахождения записей.

Доступ к нему, после того, как найдено является O (1) для всех структур. Сравнение, что Вы подразумеваете под этим? Походит на O (1) мне, в конце концов, были найдены.

8
ответ дан ypnos 24 November 2019 в 14:18
поделиться
Другие вопросы по тегам:

Похожие вопросы: