
Boost Users : 
Subject: Re: [Boostusers] [boost][heap] Which heap to use.
From: Juan RamÃrez (jramirez.uy_at_[hidden])
Date: 20160927 16:06:17
>> It's actually log n.
Actually, it is not!!
Most functions have constant complexity, except for push, which is O(n+
log(n)) = O(n).
Let me explain:
1. std::lower_bound is logarithmic in N > O( log(N) )
2. vector<T>::insert is linear in the number of elements of the vector >
O(N)
vector<T>::insert is your bottleneck here:
* In the best case it will move all the elements at the right of the
element being inserted.
* In the worst case it will have to allocate a new array and the move ALL
the elements to the new location.
Best regards
Juan
On Tue, Sep 27, 2016 at 4:14 PM, degski <degski_at_[hidden]> wrote:
> On 27 September 2016 at 18:55, Oswin Krause <Oswin.Krause_at_ruhrunibochum.
>> de> wrote:
>>
>>> Your solution has linear complexity...
>>>
>>
> It's actually log n.
>
> HAGD,
>
> degski
>
> _______________________________________________
> Boostusers mailing list
> Boostusers_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boostusers
>
 Juan :wq
Boostusers list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net