Quicksort pour trouver la médiane?

Question

Pourquoi est le pire scénario $ \ mathcal {O} \ left (n ^ 2 \ right) $ lors de l'utilisation quicksort pour trouver la médiane d'un ensemble de nombres?

• Si votre algorithme prend toujours un plus grand nombre ou inférieur à tous les numéros dans la liste ne serait pas votre algorithme échouer? Par exemple, si la liste des numéros sont:

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

  et vous continuez à choisir les nombres supérieurs à 82 $ $ ou moins de 12 $ $ pour créer des sous-listes avec, ne serait pas votre jeu toujours rester la même taille?

• Si votre algorithme prend continuellement un nombre qui crée de $ 1 sous-listes $ pourquoi est le pire des cas scénario $ \ mathcal {O} \ left (n ^ 2 \ right) $? Ne serait-efficacité linéaire étant donné que selon le maître théorème , $ d> \ log_b a $ ? * (et donc $ \ mathcal {O} \ left (n ^ d \ right) $ ou plus précisément dans ce cas $ \ mathcal {O} \ left (n \ right) $)

* Où $ d $ est l'exposant de l'efficacité (c.-à-linéaire, exponentielle, etc.), $ b $ est le facteur de la taille du problème est réduit à chaque itération, $ a $ est le nombre de sous-problèmes et $ k $ est le niveau. rapport complet: $ T (n) = \ mathcal {O} \ left (n ^ d \ right) * (\ frac {a} {b} ^ d) ^ k $

Answer 1

Quicksort est pour le tri, l'algorithme vous faites référence à un algorithme de sélection connu sous le nom Sélection rapide .

• Puisque vous ne pouvez choisir que pivot un numéro qui figure dans la liste de cas n ° 1 ne se produit jamais.
• Le pire des cas est que vous choisissez toujours un nombre qui partitions la liste en 2 listes: liste A avec un seul élément et une liste avec $ n-1 éléments de $, si tel est le cas à chaque itération vous règle uniquement un seul élément.

Alors première itération vous faites $ n opérations $, deuxième itération $ n-1 opérations $, troisième  $ n-2 opérations $, ... dernière itération 1 opération.

Quelle sa la somme de la première $ n $ nombres naturels:

$ 1 + 2 + 3 + ... + (n-2) + (n-1) + n = n (n-1) / 2 opérations de $ = O $ (n ^ 2) $