Ordenación rápida para encontrar la mediana?

Question

¿Por qué es el peor de los escenarios $ \ mathcal {O} \ left (n ^ 2 \ right) $ cuando se utiliza la clasificación rápida para encontrar la mediana de un conjunto de números?

• Si su algoritmo continuamente recoge un número mayor que o menor que todos números de la lista no dejaría que su algoritmo? Por ejemplo, si la lista de números son los siguientes:

  $ S = (12,75,82,34,55,15,51) $

  y continúa recogiendo los números de más de $ 82 $ o menos de $ 12 $ para crear sublistas con, ¿no su conjunto permanece siempre el mismo tamaño?

• Si su algoritmo recoge continuamente un número que crea sublistas de $ 1 $ por qué es el peor de los casos $ \ mathcal {O} \ left (n ^ 2 \ right) $? No sería la eficiencia ser lineal teniendo en cuenta que de acuerdo con el Maestro Teorema , d $> \ log_b un $ ? * (y, por tanto, $ \ mathcal {o} \ left (n ^ d \ right) $ o específicamente en este caso $ \ mathcal {o} \ left (n \ right) $)

* Donde $ d $ es el exponente de eficiencia (es decir, lineal, exponencial, etc.), $ b $ es el factor del tamaño de problema se reduce por en cada iteración, $ A $ es el número de subproblemas y $ k $ es el nivel. relación completa: $ T (n) = \ mathcal {O} \ left (n ^ d \ right) * (\ frac {a} {b ^ d}) ^ k $

Answer 1

ordenación rápida es para la clasificación, el algoritmo que se refiere es un algoritmo de selección conocido como de selección rápida .

• Dado que sólo puede elegir como pivote de un número que está en la caja lista # 1 nunca sucede.
• El peor caso es que tienes que elegir continuamente un número que divide la lista en 2 listas: Lista A con sólo un elemento y una lista con $ n 1-elementos $, si este es el caso en cada iteración sólo descartar una solo elemento.

Así primera iteración que hacer $ n $, operaciones segunda iteración n-1 $ $ operaciones, tercero $ N-2 operaciones $, ... última iteración 1 operación.

¿Qué Es la suma de los primeros $ $ n números naturales:

$ 1 + 2 + 3 + ... + (n-2) + (n-1) + n = n (n-1) / 2 $ operaciones = $ O (n ^ 2) $