|
![](/i/fill.gif) |
Thorsten Froehlich <tho### [at] trf de> wrote:
: The return is missing...
The standard says that the return is optional (don't ask me why).
: Total: O(n * log(n) + n * log(n))
This is equal to O(n * log(n))
: I can get:
: Total: O(2 * n + n * log(n))
This is also equal to O(n * log(n))
So in terms of O both ways are equally fast.
: 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).
: 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)).
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.
--
main(i,_){for(_?--i,main(i+2,"FhhQHFIJD|FQTITFN]zRFHhhTBFHhhTBFysdB"[i]
):_;i&&_>1;printf("%s",_-70?_&1?"[]":" ":(_=0,"\n")),_/=2);} /*- Warp -*/
Post a reply to this message
|
![](/i/fill.gif) |