Я знаю что есть std::set::lower_bound
и сложность времени O(log)
и я вижу что std::lower_bound
намного медленнее, чем std::set::lower_bound
когда работает на std::set
,
Я погуглил и нашел это:
http://en.cppreference.com/w/cpp/algorithm/lower_bound
http://en.cppreference.com/w/cpp/iterator/advance
так что ясно, что из-за std::advance
является линейным для set::iterator
, целый std::lower_bound
занимает до O(n)
,
Тем не менее, он работает намного быстрее, чем O(n)
когда я использую его (как и некоторые друзья сказали), кто-нибудь может объяснить почему или сказать мне, что это просто не так.
Гарантированная сложность для std::lower_bound()
является O(n)
на итераторах без произвольного доступа. Если этот алгоритм обнаруживает, что поиск выполняется в упорядоченном ассоциативном контейнере, он может использовать преимущества древовидной структуры, возможно, достигая лучшей сложности. Делает ли это какая-либо реализация, я не знаю.
TL; DR: всякий раз, когда контейнер предоставляет метод с тем же именем, что и существующий алгоритм, он делает это, потому что внутренняя реализация быстрее (полагаясь на свойства контейнера), и, таким образом, вы должны просто использовать его.
Проблема в том, что сложность непостоянна: O (N) какие ?
Гарантии сложности на итераторах без произвольного доступа:
В зависимости от того, является ли итерация или сравнение узким местом, это фактически меняет все!
Теоретически, в случае отсортированных ассоциативных контейнеров можно было бы std::lower_bound
воспользоваться тем, что данные уже отсортированы; однако на практике это относительно сложно. Основная проблема заключается в том, что нельзя предсказать, что предикат сравнения set
и это перешло к lower_bound
действительно одно и то же, и поэтому алгоритм должен предполагать, что это не так (если не доказано иное). И потому, что алгоритм принимает итераторы вместо диапазоны / контейнер, доказательство обратного оставлено в качестве упражнения для читателя.