|
![](/i/fill.gif) |
In article <39bab334@news.povray.org> , Warp <war### [at] tag povray org> wrote:
> : How? That is simple: I read in the words. Then sort them and then just
> : count when retrieving.
>
> But it uses more memory (specially if there are many repetitions).
Yes, it uses more memory, but in case you overlooked it, in one of my posts
I prove (using limits) that the worst case of your method will be slower for
a big enough n.
In case you start mentioning memory allocation time is not constant,
consider that I know the size of memory needed in advance, so I just need
one allocation for loading everything into memory!
> : Of course I can do this using the STL (see below)! But your example shows
> : something dangerous you forgot: the STL can trick you into thinking you
> : have found a good algorithm, but in fact yours is nearly log(n) times slower
> : than mine for most cases (for log(n) > 2)!
>
> The O-notation doesn't know the term "log(n) times slower" if the speed
> is already at least O(log(n)).
Did I use big-O notation here? I can't see it. To repeat my other post
(also mentioned above):
lim 2n lg n > lim 2n + n lg n
n->oo n->oo
=>
lim n lg n > lim 2n
n->oo n->oo
I agree that my language is not very good at explaining the speed
difference, but I think "nearly log(n) times slower" describes the above
very well!
> My version and your version have both the same O value and there's a good
> reason for this in this case: Your version can be a lot slower when the
> input is very big and there's a lot of repetition (imagine that the input
> is "word1 word2 word1 word2..." millions of times). The speed is still
> O(n*log(n)) in relation with the size of the input, but the speed factor can
> vary a lot.
Yes, but as I mentioned before, my only mistake was adding them up in the
total and leaving the big-O around it. I never said "O(n * log(n) + n *
log(n)) < O(2 * n + n * log(n))" or even "O(n * log(n)) < O(n * log(n))".
Just remove the big-O around the totals, and everything is correct!
I really should have cared more and we wouldn't have this argument about the
total big-O which has nothing to do with your implementation being slower
for a big enough n, which is all I wanted to show!!!
In fact you are falling in the same trap I fell at first when replying to
Ron: Trying to compare these two functions based on big-O notation! But
you simply cannot compare two functions with the same big-O with each other
using big-O. Other methods are needed, i.e. limits will solve the problem
for the worst case very well.
Thorsten
____________________________________________________
Thorsten Froehlich, Duisburg, Germany
e-mail: tho### [at] trf de
Visit POV-Ray on the web: http://mac.povray.org
Post a reply to this message
|
![](/i/fill.gif) |