ANALYSIS of ALGORITHMS, Bulletin Board
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Quickselect and the number of cycles.
The inversion count is a measure of the amount of
disorder in a permutation. The higher the inversion
count, the more disordered is the permutation.
A different measure of disorder in a permutation is
the number of cycles. The more cycles there are, the
more ordered is the permutation.
Question. Compute the grand average of the expected
number of cycles of a random permutation after a
random element has been selected with quickselect. The
recursion step decomposes very nicely. Compare and
contrast with the expected number of cycles of a
I wonder who will be the first to post and solve the
appropriate DE? Adelante! Auf die Plaetze, fertig,
Do You Yahoo!?
Gesendet von Yahoo! Mail - http://mail.yahoo.de
Date Prev |
Date Next |
Date Index |