Какова временная сложность std :: lower_bound с std :: set?

Я знаю что есть 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) когда я использую его (как и некоторые друзья сказали), кто-нибудь может объяснить почему или сказать мне, что это просто не так.

2

Решение

Гарантированная сложность для std::lower_bound() является O(n) на итераторах без произвольного доступа. Если этот алгоритм обнаруживает, что поиск выполняется в упорядоченном ассоциативном контейнере, он может использовать преимущества древовидной структуры, возможно, достигая лучшей сложности. Делает ли это какая-либо реализация, я не знаю.

1

Другие решения

TL; DR: всякий раз, когда контейнер предоставляет метод с тем же именем, что и существующий алгоритм, он делает это, потому что внутренняя реализация быстрее (полагаясь на свойства контейнера), и, таким образом, вы должны просто использовать его.


Проблема в том, что сложность непостоянна: O (N) какие ?

Гарантии сложности на итераторах без произвольного доступа:

  • O (N) итераций
  • O (log2 (N)) сравнения

В зависимости от того, является ли итерация или сравнение узким местом, это фактически меняет все!

Теоретически, в случае отсортированных ассоциативных контейнеров можно было бы std::lower_bound воспользоваться тем, что данные уже отсортированы; однако на практике это относительно сложно. Основная проблема заключается в том, что нельзя предсказать, что предикат сравнения set и это перешло к lower_bound действительно одно и то же, и поэтому алгоритм должен предполагать, что это не так (если не доказано иное). И потому, что алгоритм принимает итераторы вместо диапазоны / контейнер, доказательство обратного оставлено в качестве упражнения для читателя.

1

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector