Understanding "bfprt" algoritmo

Question

voglio capire "bfprt" algoritmo sul seguente esempio:

abbiamo 45 numeri distinti suddivisi in 9 gruppi con 5 elementi ciascuna.

48 43 38 33 28 23 18 13 8 

49 44 39 34 29 24 19 14 9 

50 45 40 35 30 25 20 15 10 

51 46 41 36 31 26 21 16 53 

52 47 42 37 32 27 22 17 54 

1. Il primo passo è l'ordinamento tutti i gruppi (in questo caso sono già ordinati)

2. Secondo passo in modo ricorsivo, fi trovare la "vera" mediana delle mediane (50 45 40 35 30 25 20 15 10) ovvero l'insieme sarà divisi in 2 gruppi:

   50 25 
   
   45 20 
   
   40 15 
   
   35 10 
   
   30 
   

   smistamento questi 2 gruppi

   30 10 
   
   35 15 
   
   40 20 
   
   45 25 
   
   50 
   

mediane è 40 e 15 (nel caso in cui i numeri sono ancora abbiamo preso lasciato mediana) quindi il valore restituito è 15 comunque "vera" bfprt (50 45 40 35 30 25 20 15 10) è 30, inoltre ci sono 5 elementi meno poi 15 che sono molto meno del 30% di 45 menzionati in wikipedia

e quindi T(n) <= T(n/5) + T(7n/10) + O(n) falliscono.

A proposito nell'esempio Wikipedia, ottengo risultato di ricorsione come 36. Tuttavia, il vero mediana è 47.

Quindi, penso che in alcuni casi questo ricorsione non può restituire vero bfprt. Voglio capire dov'è il mio errore.

Answer 1

Il problema è nel passaggio in cui dici di trovare la vera mediana delle mediane. Nel tuo esempio, hai avuto queste mediane:

50 45 40 35 30 25 20 15 10 

Il vero mediano di questo insieme di dati è di 30, non 15. Non si trova questo mediana suddividendo i gruppi in blocchi di cinque e prendendo la mediana di quelli mediane, ma invece chiamando ricorsivamente l'algoritmo di selezione su questo gruppo più piccolo. L'errore nella logica presuppone che mediano di questo gruppo è trovato suddividendo la sequenza sopra in due blocchi

50 45 40 35 30 

e

25 20 15 10 

poi trovare la mediana di ciascun blocco. Invece, l'algoritmo mediano-di-mediani si chiamerà ricorsivamente sul set di dati completo 50 45 40 35 30 25 20 15 10. Internamente, questo dividerà il gruppo in blocchi di cinque e li ordinerà, ecc., Ma lo farà per determinare il punto di partizione per il passo di partizionamento, ed è in questo passo di partizionamento che la chiamata ricorsiva troverà la vera mediana delle mediane , che in questo caso sarà 30. Se si usa 30 come mediana della fase di partizionamento nell'algoritmo originale, si ottiene effettivamente una divisione molto buona, come richiesto.

Spero che questo aiuti!

Answer 2

Ecco l'pseudocode per l'algoritmo mediana di mediani (leggermente modificato per soddisfare l'esempio). Lo pseudocodice in wikipedia non riesce a ritrarre i meccanismi interni della chiamata di funzione selectIdx.

Ho aggiunto commenti al codice per la spiegazione.

// L is the array on which median of medians needs to be found. 
// k is the expected median position. E.g. first select call might look like: 
// select (array, N/2), where 'array' is an array of numbers of length N 

select(L,k) 
{ 

    if (L has 5 or fewer elements) { 
     sort L 
     return the element in the kth position 
    } 

    partition L into subsets S[i] of five elements each 
     (there will be n/5 subsets total). 

    for (i = 1 to n/5) do 
     x[i] = select(S[i],3) 

    M = select({x[i]}, n/10) 

    // The code to follow ensures that even if M turns out to be the 
    // smallest/largest value in the array, we'll get the kth smallest 
    // element in the array 

    // Partition array into three groups based on their value as 
    // compared to median M 

    partition L into L1<M, L2=M, L3>M 

    // Compare the expected median position k with length of first array L1 
    // Run recursive select over the array L1 if k is less than length 
    // of array L1 
    if (k <= length(L1)) 
     return select(L1,k) 

    // Check if k falls in L3 array. Recurse accordingly 
    else if (k > length(L1)+length(L2)) 
     return select(L3,k-length(L1)-length(L2)) 

    // Simply return M since k falls in L2 
    else return M 

} 

Prendendo tuo esempio:

La mediana della funzione mediane sarà chiamata sull'intera matrice di 45 elementi come (con k = 45/2 = 22):

median = select({48 49 50 51 52 43 44 45 46 47 38 39 40 41 42 33 34 35 36 37 28 29 30 31 32 23 24 25 26 27 18 19 20 21 22 13 14 15 16 17 8 9 10 53 54}, 45/2) 

1. La prima volta M = select({x[i]}, n/10) viene chiamato, l'array {x[i]} conterrà i seguenti numeri: 50 45 40 35 30 20 15 10. In questa chiamata, n = 45, e quindi selezionare la chiamata di funzione sarà M = select({50 45 40 35 30 20 15 10}, 4)

2. La seconda volta M = select({x[i]}, n/10) si chiama, matrice {x[i]} conterrà i seguenti numeri: 40 20. In questa chiamata, n = 9 e quindi la chiamata sarà M = select({40 20}, 0). Questa chiamata selezionata restituirà e assegnerà il valore M = 20.
   
   Ora, arrivando al punto in cui hai avuto un dubbio, ora partizioniamo l'array L intorno a M = 20 con k = 4.
   
   Ricordare la matrice L qui è: 50 45 40 35 30 20 15 10.
   
   La matrice sarà suddivisa in L1, L2 e L3 secondo le regole L1 < M, L2 = M e L3 > M. Quindi:
   L1: 10 15
L2: 20
L3: 30 35 40 45 50
   
   Dal k = 4, è maggiore di length(L1) + length(L2) = 3. Quindi, la ricerca proseguirà con la seguente chiamata ricorsiva ora:
   return select(L3,k-length(L1)-length(L2))
   
   che si traduce in:
   return select({30 35 40 45 50}, 1)
   
   che restituirà 30 come risultato. (Dal momento che L ha 5 o meno elementi, quindi restituirà l'elemento in k.i, la prima posizione nell'array ordinato, che è 30).

Ora, M = 30 saranno ricevuti nella prima chiamata di funzione select sull'intera matrice di 45 elementi, e la stessa logica compartimentazione che separa l'array L intorno M = 30 si applica per ottenere infine la bfprt.

Phew! Spero di essere stato dettagliato e abbastanza chiaro da spiegare l'algoritmo della mediana dei mediani.