Perché l'algoritmo di mediana dei mediani non può utilizzare la dimensione del blocco 3?

Question

Sto lavorando all'analisi del risultato mediano deterministico partendo dal presupposto che l'input è diviso in 3 parti anziché 5 e la domanda è Dove si scompone?

la mediana deterministica algoritmo di ricerca:

SELECT (i, n)

1. Divide gli n elementi in gruppi di 5. la mediana di ciascun gruppo 5-elemento a memoria.

2. Seleziona ricorsivamente la mediana x delle mediane di gruppo ⎣n/5⎦ per essere il perno.

3. Partizione intorno al perno x. Sia k = rango (x)

4.if i = k poi tornare x

elseif i < k

poi ricorsivamente selezionare l'elemento più piccolo esimo nella parte inferiore

altro SELEZIONA ricorsivamente il (i-k) th elemento più piccolo nella parte superiore

Sono passato attraverso l'anale è l'algoritmo e credo che i passaggi 1 e 3 prenderanno O (n) dove ci vuole solo un tempo costante per trovare la mediana di 5 elementi e Step2 prende T (n/5) .so almeno 3/10 di elementi sono ≤ p, e almeno 3/10 dell'array è ≥ p, pertanto, il passaggio 4 sarà T (7n/10) e otterrà la ricorrenza. T (n) ≤ cn + T (n/5) + T (7n/10), ma quando divido gli elementi in goroup di 3, diciamo i 9 elementi e li ho divisi in gruppi tale che:

{1,2,10} {4,11,14}, {15,20,22}

Ho ottenuto le mediane 2,11,20 e la p = 11.

in generale in gruppo di cinque lascia dire g = n/5 gruppi e almeno ⌈g/2⌉ di questi (quei gruppi la cui mediana è ≤ p) almeno tre dei cinque elementi sono ≤ p. quindi il numero totale di elementi ≤ p è almeno 3⌈g/2⌉ ≥ 3n/10. MA in un gruppo di 3 possiamo ottenere che tutti e tre gli elementi siano MENO di p. e qui penso che l'algoritmo si romperà !!

Ho avuto un'idea corretta ???

Answer 1

In un gruppo di 3, come per i gruppi di 5, circa la metà dei gruppi avrà il loro elemento mediano inferiore alla mediana dei mediani, quindi in tali gruppi è possibile scartare gli elementi inferiori alla loro mediana. Nel tuo caso, (1,2,10) ha una mediana inferiore a 11, quindi puoi scartare 1 e 2.

Dove penso che le cose si interrompano per gruppi di 3 è nel costo. 3 (floor (floor (n/5)/2 - 2) che è circa 3n/10 diventa 2 (floor (floor (n/3)/2 -2) o giù di lì, che è approssimativamente n/3. 7n/10 diventa 2n/3. floor (n/5) diventa floor (n/3), quindi invece di 7cn/10 + 2cn/10 = 9cn/10 otterrai solo 2cn/3 + cn/3 = cn, e invece di T (n) < = cn avrai qualcosa in cui dovrai guardare da vicino i termini che non implicano c, e potresti finire per mostrare che dopo tutto non è lineare.

Sembra che tu in effetti riesca a gettare via un po 'più di elementi in ogni fase della ricorsione, ma la ricorsione divide la quantità di lavoro lasciata da 3, non 5, e questo non è sufficiente per pareggiare.