StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>This is almost a year later, but I think I have an answer: partial order discovery.</p> <p>Think about sorting on a total ordering for a moment. You have a sequence of n objects (we will assume they are distinct), and a comparison operation which tests two elements to see if one is less than or equal to the other.</p> <p>You are trying to discover which permutation the elements are in. There are n! possible permutations, so you're trying to discover a number between 1 and n!. Each comparison gives you one bit of information. To discover a number between 1 and n! requires discovering log(n!) bits. Therefore the number of comparisons required is also log(n!) bits, or:</p> <p>log(n!) = n log n + o(n log n) = Ω(n log n) bits</p> <p>(All logarithms are, of course, in base 2.)</p> <p>You cannot do better than this. If each query gives you one bit of information, and you need to discover at least Ω(n log n) bits, then you need Ω(n log n) comparisons. If you think you can do better, take it up with Shannon, Chaitin and Kolmogorov.</p> <p>But what's even better is that algorithms are known which can do it even in the worst case (e.g. heap sort). In that sense, heap sort is asymptotically optimal.</p> <p>(Note that you can do better if you have a query operation which returns more than one bit of information. If you can come up with one that returns Ω(log n) bits, for example, then you should be able to sort in Ω(n) time. See radix sort for more details.)</p> <p>This analysis works with all sorts of algorithms. Finding a single thing in a sequence of n things requires discovering a number between 1 and n, which means discovering log n + O(1) bits. If your query operation returns one bits, then it takes Ω(log n) queries to do the search. (See binary search for details.)</p> <p>I think you can see where I'm going with this.</p> <p>Now suppose you have n elements which have a partial order relation on them, but you don't know what it is and want to find out. What you do have, though, is a query which compares two elements x and y, and returns "true" if x is less than or equal to y in the partial order.</p> <p>There is an obvious algorithm to discover the partial order which takes Ω(n^2) time: simply compare each element against each other element.</p> <p>But is this optimal? Well, the query operation returns one bit of information. The number of partial orders on n elements is given by <a href="http://oeis.org/A001035" rel="nofollow">Sloane's A001035</a>. If I'm reading it right, this sequence is Ω(2^(n^2)), which means that to discover a partial order, you need:</p> <p>Ω(log 2^(n^2)) = Ω(n^2) bits</p> <p>That is, you can't do better than Ω(n^2) time, so this is an asymptotically optimal algorithm.</p> <p>"So", I hear you ask, "I buy the fact that the size of the input is n. But isn't the size of the <em>output</em> O(n^2), so it's actually a linear algorithm in some deep technical sense?"</p> <p>Well... maybe. I don't really have time to go into the details right now, but I'll answer it with a question.</p> <p>In the case of plain old sorting, we might be given n <em>distinct</em> elements. To be distinct, they need to be labelled with n <em>distinct</em> labels. Storing n distinct labels means storing n numbers, each of which is between 1 and n. Each of those numbers requires log n bits to represent it, so the total size of the problem is n log n <em>bits</em>. So why don't we say that heap sort is linear in the size of the problem?</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload