« La ordenación superadaptativa contraataca.
II CUSL »

Alguíen confirma mi punto de vista en wikipedia.

Lo que decía sobre la cota de los algoritmos de ordenación, explicado aquí con una bonita demostración.

Proof of the lower bound for the asymptotic running time of comparison sort algorithms

The worst case running time of any comparison sort algorithm is Ω(nlgn)

Let T be the decision tree for all possible comparisons between elements of a list X[1\dots n]. So T is complete and the label of each vertex v of the tree are of the form xi:xj and v is source of two edges labeled \ge and < . The comparisons made by a sorting algorithm running over X corresponds to a path from the root of T to a leaf. One should note that for each possible permutation P of the elements in X there is such a path. So T has at least n! leaves. We know that T is a binary tree, so it has a maximum of 2h leaves, where h is it’s height. We have 2^h \ge n! and
  \begin{array}{ccl} \lg(2^h) & = & h\\  & \ge & \lg(n!)\\ & = & \lg (n\times (n - 1)\dots 2)\\ & \ge & \lg (\underbrace{\frac{n}{2}\times \frac{n}{2} \dots \frac{n}{2}}_{\frac{n}{2} times})\\ & = & \lg (\frac{n}{2}^\frac{n}{2})\\ & = & \frac{n}{2} \lg (n) - 1\\ & \ge & \frac{1}{4}n \lg n \end{array}.

Summarizing, h = Ω(nlgn)

This entry was posted on Saturday, September 8th, 2007 at 10:56 and is filed under General. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

One Response to “Alguíen confirma mi punto de vista en wikipedia.”

  1. javifields Says:
    September 8th, 2007 at 12:16

    si, es lo mismo que intentaba explicarte yo en http://azrael.cauterized.net/2007/04/12/algoritmos-de-ordenacion/#comments, donde te ponía también un enlace a estas transparencias…

Leave a Reply