Mediana delle medie

Question

Ho letto le statistiche degli ordini per trovare l'elemento k-th più piccolo (o più grande) in una matrice di dimensione n nel tempo lineare O (n).

C'è un passo che è necessario per trovare la mediana delle mediane.

1. Dividere l'array in [n/5] parti. Ogni parte ha 5 elementi.
2. Trova la mediana in ogni parte. (Abbiamo [n/5] numeri ora)
3. Ripeti i passaggi 1 e 2 finché non abbiamo solo l'ultimo numero. (Cioè ricorsiva)

T (n) = T (n/5) + O (n) e possiamo ottenere T (n) = O (n).

Ma è proprio vero che il numero che otteniamo non è la mediana delle mediane, ma la mediana delle mediane delle mediane delle mediane delle mediane delle mediane, se abbiamo una vasta gamma.

Si prega di considerare un array con 125 elementi.

In primo luogo, è diviso in 25 parti e troviamo 25 mediane. Quindi, suddividiamo questi 25 numeri in 5 parti e troviamo 5 mediane, Infine, otteniamo il numero che è mediano delle mediane delle mediane. (Non mediana delle mediane)

Il motivo per cui mi interessa è che, posso capire che ci sono al massimo circa [3/4] * n elementi che sono più piccoli (o più grandi) della mediana delle mediane. Ma cosa succede se non è la mediana delle mediane ma la mediana delle mediane delle mediane? Nel caso peggiore ci devono essere meno elementi che sono più piccoli (o più grandi) del pivot, il che significa che il perno è più vicino al limite dell'array.

Se disponiamo di un array MOLTO grande, abbiamo trovato la mediana delle mediane delle mediane delle mediane delle mediane delle mediane. Nel peggiore dei casi il pivot che abbiamo trovato può essere ancora molto vicino al limite e qual è la complessità temporale in questo caso?

Ho creato un set di dati di 125 elementi. Il risultato è 9?

0.8 0.9 1 inf inf 
1.8 1.9 2 inf inf 
6.8 6.9 7 inf inf 
inf inf inf inf inf 
inf inf inf inf inf 

2.8 2.9 3 inf inf 
3.8 3.9 4 inf inf 
7.8 7.9 8 inf inf 
inf inf inf inf inf 
inf inf inf inf inf 

4.8 4.9 5 inf inf 
5.8 5.9 6 inf inf 
8.8 8.9 9 inf inf 
inf inf inf inf inf 
inf inf inf inf inf 

inf inf inf inf inf 
inf inf inf inf inf 
inf inf inf inf inf 
inf inf inf inf inf 
inf inf inf inf inf 

inf inf inf inf inf 
inf inf inf inf inf 
inf inf inf inf inf 
inf inf inf inf inf 
inf inf inf inf inf 

dove inf indica che il numero è abbastanza grande.

Answer 1

Denotiamo tuo bfprt di mediane di ... come [mediana di] * = M.

In primo luogo, credo che l'algoritmo di mediana dei mediani (per selezionare un buon pivot) non sia ricorsivo. L'algoritmo è la seguente:

1. Split gli elementi in gruppi di 5
2. la mediana di ciascun gruppo
3. Trova la bfprt e usarlo come perno.

bfprt sarà più piccolo 3n/10 elementi e grande di un altro 3n/10 elementi, non 3n/4. Hai n/5 numeri dopo aver selezionato le mediane. La mediana della mediana è maggiore/minore della metà di quei numeri, che è n/10. Ognuno di questi numeri è una mediana stessa, quindi è maggiore/minore di 2 numeri, dandoti altri 2n/10 numeri. Ora in totale, ottieni n/10 + 2n/10 = 3n/10 numeri.

Per affrontare la seconda domanda, dopo aver raccolto il gruppo di 5 di nel tuo esempio set di dati e calcolo delle loro mediane, avremo la seguente sequenza:

1, 2, 7, inf, inf 
3, 4, 8, inf, inf 
5, 6, 9, inf, inf, 
inf, inf, inf, inf, inf, 
inf, inf, inf, inf, inf. 

Così il bfprt sarebbe davvero 9.

tuo proposto [mediana di] * runtime dell'algoritmo sarà:

T(n) = O(n * log(n)) 

Ora proviamo ad analizzare quanti numeri abbiamo meno/più grande di M. Abbiamo i seguenti gruppi:

• profondità 1: n/5 elementi tutti mediane
• profondità 2: n/25 elementi tutti mediane
• ...
• profondità i: n/(5^i) elementi tutti mediane

Ogni gruppo è inferiore/superiore a 2 elementi di profondità precedente, che è meno/maggiore di 2 elementi di profondità precedente, e così via:

Calcolando in totale, otteniamo che il nostro M è maggiore/minore di (n * (2^k) + k * n)/((2^k) * (5^k)). Per profondità = 1 ottieni mediana delle mediane, che è 3n/10.

Ora supponendo che la profondità è [log_5 (n)], cioè n = 5^k, otteniamo:

5^k * (k + 2^k)/(5^k * 2^k) che è -> 1.