complessità di un algoritmo di ricerca randomizzato

Question

Considerare il seguente algoritmo di ricerca randomizzato su un array ordinato a di lunghezza n (in ordine crescente). x può essere un qualsiasi elemento dell'array.

size_t randomized_search(value_t a[], size_t n, value_t x) 
    size_t l = 0; 
    size_t r = n - 1; 
    while (true) { 
     size_t j = rand_between(l, r); 
     if (a[j] == x) return j; 
     if (a[j] < x) l = j + 1; 
     if (a[j] > x) r = j - 1; 
    } 
} 

Qual è il valore di attesa della Big Theta complexity (delimitata sotto e sopra) di questa funzione quando x è selezionato casualmente da a?

Anche se questo sembra essere log(n), ho effettuato un esperimento con conteggio di istruzioni, e abbiamo scoperto che il risultato cresce un po 'più veloce di log(n) (secondo i miei dati, anche (log(n))^1.1 meglio montare il risultato).

Qualcuno mi ha detto che questo algoritmo ha un esatto grande complessità theta (quindi ovviamente log(n)^1.1 non è la risposta). Quindi, potresti per favore dare la complessità del tempo insieme al tuo approccio per dimostrarlo? Grazie.

---

Update: i dati dal mio esperimento

log(n) risultato in forma di Mathematica:

log(n)^1.1 risultato in forma:

Answer 1

Se sei disposto a passare al conteggio dei confronti a tre vie, posso dirti la complessità esatta.

Supponiamo che la chiave sia in posizione i e voglio conoscere il numero previsto di confronti con la posizione j. Io sostengo che la posizione j è esaminata se e solo se è la prima posizione tra io e j inclusive da esaminare. Poiché l'elemento pivot viene selezionato in modo uniforme a caso ogni volta, ciò avviene con probabilità 1/(| i - j | + 1).

La complessità totale è l'attesa oltre i < - {1, ..., n} di {sum_ j = 1}^n 1/(| i - j | + 1), che è

sum_{i=1}^n 1/n sum_{j=1}^n 1/(|i - j| + 1) 
= 1/n sum_{i=1}^n (sum_{j=1}^i 1/(i - j + 1) + sum_{j=i+1}^n 1/(j - i + 1)) 
= 1/n sum_{i=1}^n (H(i) + H(n + 1 - i) - 1) 
= 1/n sum_{i=1}^n H(i) + 1/n sum_{i=1}^n H(n + 1 - i) - 1 
= 1/n sum_{i=1}^n H(i) + 1/n sum_{k=1}^n H(k) - 1 (k = n + 1 - i) 
= 2 H(n + 1) - 3 + 2 H(n + 1)/n - 2/n 
= 2 H(n + 1) - 3 + O(log n/n) 
= 2 log n + O(1) 
= Theta(log n). 

(log indica log naturale qui.) Nota il -3 nei termini di ordine basso. Questo fa sembrare che il numero di confronti stia crescendo più velocemente di logaritmico all'inizio, ma il comportamento asintotico impone che si livella. Prova ad escludere la piccola n e a correggere le tue curve.

Answer 2

Supponendo che rand_between esegua il campionamento da una distribuzione di probabilità uniforme in tempo costante, il tempo di esecuzione previsto di questo algoritmo è Θ (lg n). Schizzo informale di una prova: il valore atteso di rand_between(l, r) è (l+r)/2, il punto medio tra di loro. Si prevede quindi che ogni iterazione salti la metà dell'array (supponendo che la dimensione sia una potenza di due), proprio come farebbe una singola iterazione di ricerca binaria.

Più formalmente, prendendo a prestito da un'analisi di quickselect, osservare che quando si sceglie un punto medio a caso, la metà del tempo che sarà tra ¼ n e ¾ n. Né il sottoarray sinistro né quello destro hanno più di ¾ n elementi. L'altra metà del tempo, né ha più di n elementi (ovviamente). Questo porta ad una relazione di ricorrenza

T(n) = ½T(¾n) + ½T(n) + f(n) 

dove f (n ) è la quantità di lavoro in ogni iterazione. Sottraendo ½T (n) da entrambi i lati, quindi raddoppiando entrambe le parti, abbiamo

½T(n) = ½T(¾n) + f(n) 
T(n) = T(¾n) + 2f(n) 

Ora, dal momento che 2F (n) = Θ (1) = Θ (n ᶜ log⁰ n), dove c = log (1) = 0, segue dal teorema che T (n) = Θ (n ⁰ lg n) = Θ (lg n ).