Re: Too Many Packages [was Re: Splitting locales...]
Hi, I've follow this thread without a great concentration, but now ...
That radix sort sound to me as an absurd: I've read a prove of that
lower bound of sorting in a sequencial architetture is O(n log n)
[Prof. Paolo Zellini, CNR] . I don't remember literally the prove, but
it was correct (my professor Milvio Capovani, second it, and me too of
course :).
So, now I've a problem: cause I've surely missunderstood what the
matter here and what is for radix sort, I've loose where's documented
that alghoritms and how it can "sort" something in linear time (if it
do sort at all).
I'm interested in parallel alghorithms so, if radix sort is such an
alghoritms, I'll be happy to read about it. If it isn't and does some
strange work over string, require more space and such I'll be happy to
known it the same (curiosity).
Please don't flame me, I do not intend do offend no one, it was just a
missunderstood ... probably I've an idea of what radix sort is and i
was asking myself if I'm right.
Thank you.
Daniele.
On Mon, Oct 09, 2000 at 08:14:20PM -0700, Thomas Bushnell, BSG wrote:
> tb@becket.net (Thomas Bushnell, BSG) writes:
>
> > But if you calculate that way, then mergesort now takes O(n log^2 n).
> > In other words, there is a hidden factor for mergesort, because
> > comparing items isn't a constant operation, but is log n in the size
> > of the items.
>
> To be more precise, suppose we are sorting N digit strings with max
> M. (Each digit string represents a number, and the largest number is
> M; the strings are thus log(M) digits long.)
>
> Real computers have constant time comparison operations only for
> strings of finite length. Comparing strings of unbounded length will
> take log(M) time. Now mergesort takes O(n log n) comparisons, but
> each one is (log M) in length. So this means that mergesort is now
> O(N log(N) log(M)) in time.
>
> Radix sort requires O(N log(M)) total time, by the argument you gave.
>
> If you want to pretend that comparisons are constant time, you can do
> that by factoring out the log(M) time, but only by saying the strings
> are of limited length, in which case you also factor out the same
> log(M) time from the radix sort.
>
>
>
> --
> To UNSUBSCRIBE, email to debian-devel-request@lists.debian.org
> with a subject of "unsubscribe". Trouble? Contact listmaster@lists.debian.org
--
Daniele Cruciani <cruciani@cli.di.unipi.it>
Universita` di Pisa - Informatica -
http://www.cli.di.unipi.it/~cruciani/
Reply to: