Недавно, работая над проблемой программирования в C ++, я наткнулся на что -то интересное. Мой алгоритм использовал действительно большой набор и использовал бы std :: lower_bound на нем много раз. Однако, после того, как я подал решение, вопреки математике, которую я сделал на бумаге, чтобы доказать, что мой код был достаточно быстрым, он оказался слишком медленным. Код выглядел примерно так: < /p>
using namespace std;
set s;
int x;
//code code code
set::iterator it = lower_bound(s.begin(),s.end(),x);
< /code>
Однако, получив подсказку от приятеля, чтобы использовать Set :: lower_bound, рассматриваемый алгоритм, о котором идет речь быстрее, чем раньше, и он последовал за моей математикой. Бинарный поиск после изменения: < /p>
set::iterator it = s.lower_bound(x);
< /code>
Мой вопрос: в чем разница между этими двумя? Почему один работает намного, намного быстрее, чем другой? Разве Lower_bound не должна быть бинарной функцией поиска, которая имеет сложность O (log2 (n))? В моем коде это оказалось намного медленнее, чем это.
Подробнее здесь: https://stackoverflow.com/questions/318 ... ower-bound
