Re: stable algorithm with complexity O(n)

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



On 14Dec2008 01:42, Marko Vojinovic <vvmarko@xxxxxxxxxxx> wrote:
| On Sunday 14 December 2008 00:17, Cameron Simpson wrote:
| > On 13Dec2008 19:22, David Hl??ik <david@xxxxxxxxx> wrote:
| > | 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) .
| >
| > Since sorting in general is O(n log n), I don't see how you're going to
| > do in in O(n) unless there's something special about your number range
| > you've not told us about. A stable sort limits your choices somewhat
| > more, but not a lot - it usually just imposes a little more care on the
| > comparison stage for most algorithms.
| >
| > I think you need to define the problem in more detail.
| 
| There is the generation counter algorithm. It is O(n), and relies on the fact 
| that one knows the boundaries of the possible elements of the dataset (and 
| it's domain). Basically, you simply count the number of appearances of every 
| element in your set. It's just a single for-loop.

Hmm. Cute. But what about to insertion cost of updating the counters?
That's where this kind of thing tends to come back on you.

| Of course, if you don't know this additional data, the general sort is
| O(n ln n) at best. However, the OP did state that he needs to sort integers 
| from the interval [1,n^2] which is enough for generation counter.
| 
| The OP also posted this to the CentOS list as well, and I gave him a more 
| thorough explanation there. You might want to take a look. ;-)

I'm not on that list (and am having trouble finding out how to join).
Can you send me a copy or point me to an archive URL?

Cheers,
-- 
Cameron Simpson <cs@xxxxxxxxxx> DoD#743
http://www.cskk.ezoshosting.com/cs/

-- 
fedora-list mailing list
fedora-list@xxxxxxxxxx
To unsubscribe: https://www.redhat.com/mailman/listinfo/fedora-list
Guidelines: http://fedoraproject.org/wiki/Communicate/MailingListGuidelines
[Index of Archives]     [Older Fedora Users]     [Fedora Announce]     [Fedora Package Announce]     [EPEL Announce]     [Fedora Magazine]     [Fedora News]     [Fedora Summer Coding]     [Fedora Laptop]     [Fedora Cloud]     [Fedora Advisory Board]     [Fedora Education]     [Fedora Security]     [Fedora Scitech]     [Fedora Robotics]     [Fedora Maintainers]     [Fedora Infrastructure]     [Fedora Websites]     [Anaconda Devel]     [Fedora Devel Java]     [Fedora Legacy]     [Fedora Desktop]     [Fedora Fonts]     [ATA RAID]     [Fedora Marketing]     [Fedora Management Tools]     [Fedora Mentors]     [SSH]     [Fedora Package Review]     [Fedora R Devel]     [Fedora PHP Devel]     [Kickstart]     [Fedora Music]     [Fedora Packaging]     [Centos]     [Fedora SELinux]     [Fedora Legal]     [Fedora Kernel]     [Fedora OCaml]     [Coolkey]     [Virtualization Tools]     [ET Management Tools]     [Yum Users]     [Tux]     [Yosemite News]     [Gnome Users]     [KDE Users]     [Fedora Art]     [Fedora Docs]     [Asterisk PBX]     [Fedora Sparc]     [Fedora Universal Network Connector]     [Libvirt Users]     [Fedora ARM]

  Powered by Linux