Ищет ли ключ std::map O(1)? Я думал, что это так, пока я не подумал об этом больше. Он основан на реализации дерева, поэтому время поиска должно быть O (log N), правильно?
И возможно ли, чтобы O (1) искал строковый ключ, возможно, std::unordered_map?
Сложность поиска для std::map составляет O(log N) (логарифмический в размер контейнера).
Согласно параграфу 23.4.4.3/4 стандарта С++ 11 для std::map::operator []:
Сложность: логарифмическая.
Сложность поиска std::unordered_map составляет O(1) (постоянная) в в среднем случае и O(N) (линейно) в худшем случае.
Согласно параграфу 23.5.4.3/4 стандарта C++11 на std::unordered_map::operator []
Сложность: в среднем O(1), в худшем случае O(
size()).
ПРИМЕЧАНИЕ:
Если ваш вопрос касается только сложности вычислений, то то, что написано выше, должно ответить на него. Вычислительная сложность операции, по сути, измеряется размером контейнера (количеством содержащихся в нем элементов).
Однако, если вы ищете способ выполнения поиска O(1) в контейнере, который использует строковые ключи и где сложность поиска постоянна относительно длины строки, а не к размеру контейнера, то ответ таков, что std::unordered_map не будет соответствовать вашим требованиям.
Чтобы найти ключ, сначала необходимо создать его хэш; когда ключ является строкой, сама эта операция может быть линейной по размеру строки. Затем реализация должна сравнить ключ со всеми строковыми ключами в одном сегменте, и каждое из этих сравнений, в свою очередь, линейно зависит от размера этих строк.
unordered_map по-прежнему будет варьироваться в зависимости от размера строк, не так ли? Для каждого поиска потребуется генерация хэша и сравнение ключей для каждого элемента в корзине.
- person Mark Ransom; 17.04.2013
O вообще этого не выражает, но, похоже, это вызывает беспокойство в вопросе.
- person Mark Ransom; 17.04.2013
O(1) с помощью строкового ключа, может намекнуть на то, что пользователь в этом заинтересован.
- person David Rodríguez - dribeas; 17.04.2013
Да, действительно std::map будет O(log N) и std::unordered_map будет иметь среднюю сложность с постоянным временем и O(N) в худшем случае, если будет слишком много хеш-коллизий.
O(1). Довольно легко построить вырожденный случай, когда это O(N).
- person doublep; 17.04.2013
В основном std::map реализован с использованием красно-черного дерева. В красно-черном дереве операция вставки и удаления занимает O(LogN) времени, поэтому в std::map временная сложность составляет O(LogN) каждого элемента.
std::unodered_map реализован с использованием хеширования, где каждая операция занимает время O(1).
