On 03/08/11 22:18, Ion Gaztañaga wrote:
El 03/08/2011 19:27, Phil Endecott escribió:
Hi Ion,
(Note typo: i,j vs, first,last)
Thanks.
What implementation are you assuming to get that complexity? It seems to me that it is worse than it could be if you implement it something like this (PSEUDO-CODE):
I took the first part from SGI documentation (the standard also says "N log(a.size() + N)") since I was implementing it as a loop of simple insertions:
http://www.sgi.com/tech/stl/MultipleAssociativeContainer.html
Average complexity for insert range is at most O(N * log(size() + N)), where N is j - i.
The second part is vector insertion time in case is a vector front insertion by N. I think it should prepend "at most ".
Your code should be:
N ¿? //insert + O(N log(N)) //sort (comparisons) + O(size()+N) //inplace_merge (comparisons) if using intermediate memory
I think (I'm not an expert and it could depend on N's size) your code has lower complexity (and an additional allocation, I think it could be faster depending on the cost of the copies).
No; the existing complexity is better. Let S=size() and N=aS. You have N log(S+N) = aS log(S(1+a)) = S(a log(S) + a log(1+a)) < S(a log(S) + 1+2a+a log(a)) (If you don't think that's obvious see <http://www.wolframalpha.com/input/?i=a+Log[1%2Ba]%3C1%2B2a%2Ba+Log[a]>) = S(1+2a + a(log(S)+log(a))) = S + aS(2 + log(aS)) = S + N(2 + log(N)) = N + N log(N) + S + N which is the alternative. Of course, there are constant factors to worry about, but my gut says they work in favour of the existing implementation too. John Bytheway