Quicksort per trovare mediana?

Question

Perché è il peggiore scenario di $ \ mathcal {O} \ left (n ^ 2 \ right) $ quando si utilizza Quicksort per trovare la mediana di un insieme di numeri?

• Se l'algoritmo prende continuamente un numero maggiore o minore di tutti numeri nella lista non sarebbe il vostro algoritmo fallire? Per esempio, se l'elenco dei numeri sono:

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

  e si continua a raccogliere i numeri maggiori di $ $ 82 o meno di $ 12 $ per creare sottoliste con, non sarebbe il set rimane sempre della stessa dimensione?

• Se l'algoritmo prende continuamente un numero che crea sottoliste di $ 1 $ per questo è lo scenario peggiore $ \ mathcal {O} \ left (n ^ 2 \ right) $? Non sarebbe l'efficienza essere lineare considerando che secondo il teorema , $ d> \ log_b un $ ? * (e quindi $ \ mathcal {o} \ left (n ^ d \ right) $ o specificamente in questo caso $ \ mathcal {o} \ left (n \ right) $)

* Dove $ d $ è l'esponente efficienza (cioè lineare, esponenziale ecc), $ b $ è il fattore la dimensione del problema viene ridotto ad ogni iterazione, $ a $ è il numero di sottoproblemi e $ k $ è il livello. Rapporto completa: $ T (n) = \ mathcal {O} \ left (n ^ d \ destra) * (\ frac {a} {b ^ d}) ^ k $

Answer 1

Quicksort è per l'ordinamento, l'algoritmo si fa riferimento a un algoritmo di selezione nota come Selezione rapida .

• Dal momento che si possono raccogliere solo come perno un numero che è nella lista caso # 1 non accade mai.
• Il caso peggiore è che si sceglie continuamente un numero che partizioni la lista in 2 liste: Lista A con un solo elemento e una lista con $ n-1 $ elementi, se questo è il caso in ogni iterazione si regola solo un singolo elemento.

Quindi, prima iterazione si fa $ n $, operazioni di iterazione secondo $ operazioni di $ 1-n, terzo $ n-2 $ operazioni, ... ultima iterazione 1 operazione.

Quali sua la somma dei primi $ n $ numeri naturali:

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