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
On Wed, Nov 30, 2011 at 9:06 PM, Thijs (M.A.) van den Berg <thijs@sitmo.com>wrote: 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