Duncan Booth schrieb:
"Diez B. Roggisch" <de...@nospam.web.de> wrote:
David Hlá�ik schrieb:
Hi guys,
i am really sorry for making offtopic, hope you will not kill me, but
this is for me life important problem which needs to be solved within
next 12 hours..
I have to create stable algorithm for sorting n numbers from interval
[1,n^2] with time complexity O(n) .
Can someone please give me a hint. Would be very very thankful!
Unless I grossly miss out on something in computer science 101, the
lower bound for sorting is O(n * log_2 n). Which makes your task
impossible, unless there is something to be assumed about the
distribution of numbers in your sequence.
Who has given you that assignment - a professor? Or some friend who's
playing tricks on you?
I think you must have fallen asleep during CS101. The lower bound for
sorting where you make a two way branch at each step is O(n * log_2 n), but
if you can choose between k possible orderings in a single comparison you
can get O(n * log_k n).
To beat n * log_2 n just use a bucket sort: for numbers with a known
maximum you can sort them digit by digit for O(n log_k n), and if you don't
restrict yourself to decimal then k can be as large as you want, so for the
problem in question I think you can set k=n and (log_n n)==1 so you get
O(n)
Thanks. I *totally* forgot about that.
Diez
--
http://mail.python.org/mailman/listinfo/python-list
