Вопрос:
Какова временная сложность std :: map? И выродится ли он в худшем случае? Или это решение по реализации, мы не можем это знать?
Лучший ответ:
Подсказки пропорциональны log (N). В типичном случае (реализация как красно-черное дерево) количество сравнений может быть в два раза логарифмом 2 N.
Вставки, как правило, также пропорциональны Log 2 N, но есть специальное положение, когда вы вставляете несколько элементов, которые уже в порядке 1. В этом случае вы можете указать “подсказку” для того, где будет происходить вставка. Когда эта подсказка верна, каждая вставка (амортизируется) O (1) вместо O (Log N), поэтому вставка диапазона элементов в отсортированном порядке является линейной, а не N log (N). Указанный вами намек – это итератор в позицию сразу после элемента, который нужно вставить.
Например, если у вас есть несколько элементов в файле в отсортированном порядке, и вы хотите вставить их в карту, вы можете указать your_map.end() как “подсказку”, а построение карты будет иметь O (N ) сложность вместо сложности O (N Log N).
1. Технически это применяется в любое время, когда вы вставляете элементы, а не только в том случае, когда вы их вставляете по порядку – но, безусловно, наиболее распространенным случаем, когда у вас есть разумный “намек”, является то, что вы вставляете элементы в порядок.
Ответ №1
Обычно для операций задается временная сложность. В вашем случае поиск и вставка кажутся релевантными.
См. Http://www.sgi.com/tech/stl/complexity.html для гарантированных дополнений контейнеров STL. И это http://www.sgi.com/tech/stl/AssociativeContainer.html в Ассоциативных контейнерах.
Другой источник находится здесь:
- http://www.cplusplus.com/reference/map/map/find/ → Логарифмический размер.
- http://www.cplusplus.com/reference/map/map/insert/ → Если вставлен один элемент, логарифмический по размеру в целом, но амортизируется постоянным, если дается подсказка, и заданное положение является оптимальным.
поиск std :: map – это log (количество элементов на карте).
Ответ №2
Это зависит от реализации, вы не можете связать сложность любого вида с std::map просто просмотрев спецификации языка.
Обычно std::map выполнена в виде красно-черного дерева, и вы можете найти всю информацию о свойствах Big-O этого вида контейнеров здесь.
В частности, существуют менее популярные альтернативы стандартным библиотекам, поставляемым с популярными компиляторами, такими как msvc или gcc, которые реализуют этот вид контейнеров с B-tree s, что приводит к снижению использования памяти из-за того, что B-дерево обычно занимает меньше память, что RB-дерево.
Например, нажмите здесь.
Ответ №3
если вы спрашиваете о сложности времени поиска для std :: map, то это будет O (log (n)), поскольку stl реализовала библиотеку std :: map в виде дерева (бинарного дерева) datastructure.
Дополнительная информация здесь: http://www.cplusplus.com/reference/map/map/
Здесь также широко используется std :: unordered_map, который будет вашим хэшмапом (без упорядочивания) с частотой поиска O (1), однако, используя больше памяти, чем Tree для дизайна структуры данных.
