Serhio wrote:
> Здравствуйте, MaximE, Вы писали:
>
> ME>Возможно, что сортировать вектор не очень удачное решение, по сравнению с использованием upper/lower_bound. После вставки sort будет перелопачивать весь массив, lower_bound же найдет тебе нужное место вставки бинарным поиском.
>
> ME>Хотя опять же, сложность lower_bound — гарантировано log2(n), быстрой сортировки std::sort — в среднем c * n * log2(n), в худшем — n ** 2...
>
> А вставку элемента в середину вектора, в случае использования upper/lower_bound, вы учли?
log2(n)
+ c * n / 2
--
Maxim Yegorushkin
Those who do not understand Unix are condemned to reinvent it, poorly. © Henry SpencerPosted via RSDN NNTP Server 1.9
