Re: [boost] [stl_ext_adv] ] Interest in advanced data structures

Subject: Re: [boost] [stl_ext_adv] ] Interest in advanced data structures
From: Vadim Stadnik (vadimstdk_at_[hidden])
Date: 2011-11-30 06:01:58

On Wed, Nov 30, 2011 at 9:06 PM, Thijs (M.A.) van den Berg
<thijs_at_[hidden]>wrote:

> > The examples demonstrate how to improve the computational complexity from
> > O(N) to O(log N) in the following applications and problems:
> >
> > - numerical integration.
> > - calculation of mean value and standard deviation;
> > - calculation of weighted mean value;
>
> I think O(log N) is misleading.
> Problem:  I  want to estimate the mean of N numbers in a file on my disk.
> Clearly I should al least present all of the number in that file al least
> once  (O(N)) to a black box algorithm that computes the mean?
>
> Thank you for this comment.
You are right, if you mean the cost of construction of an advanced data
structure, it is O(N log N). As soon as the required data have been written
the sum and mean value of any consecutive elements can be found in O(log N)
time. Please, have a look at performance tests of the fast algorithm
accumulate() in the section:

http://dl.dropbox.com/u/51041088/stl_ext_adv_doc/doc/performance.html

Also, you can use example or test code to notice the difference in the
performance of standard and fast algorithms accumulate().

Regards,

Vadim Stadnik