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

Subject: Re: [boost] [stl_ext_adv] ] Interest in advanced data structures
From: Thijs (M.A.) van den Berg (thijs_at_[hidden])
Date: 2011-11-30 05:06:24

> Hi all,
> 
> Advanced data structures (ADS) offer useful STL extensions that are not
> possible or not efficient with basic data structures, such as arrays,
> linked lists and red-black trees.
> 
> The project
> 
> https://github.com/vstadnik/stl_ext_adv
> 
> http://dl.dropbox.com/u/51041088/stl_ext_adv_doc/index.html
> 
> focuses mainly on a generalized and unified computer representation of
> sequences using the augmented B+ trees. It provides the following STL
> extensions
..
> 
> 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?