Sto cercando di capire i concetti di base degli algoritmi attraverso le classi offerte in Coursera (in bit e pezzi), I trovato l'algoritmo deterministico di selezione del tempo lineare che funziona come segue:
- Seleziona (A, n, i)
- Se n = 1 restituisci A [1].
- p = ChoosePivot (A, n)
- B = Partizione (A, n, p)
- Supponiamo che p sia l'elemento jth di B (vale a dire, la statistica di ordine j di A). Lasciare che la "prima parte di B" denoti
il suo primo j - 1 elementi e la "seconda parte" i suoi ultimi elementi n - j.
- Se i = j, restituisci p.
- Se io < j, return Seleziona (1a parte di B, j - 1, i).
- Else return Select (2a parte di B, n - j, i - j).
E ordina internamente l'array nella subroutine ChoosePivot per calcolare la mediana della mediana utilizzando un algoritmo di ordinamento basato sul confronto. Ma il limite inferiore non è sul parsing basato sull'ordinamento O(nlogn) ? Quindi, come sarebbe possibile per noi ottenere il O(n) per l'intero algoritmo allora?
Mi sto perdendo qualcosa qui?