come calcolare la complessità della ricerca binaria

Ho sentito qualcuno dire che dal momento che la ricerca binaria dimezza l’input richiesto per la ricerca, quindi è log (n) algoritmo. Dal momento che non provengo da un background matematico, non sono in grado di relazionarmi ad esso. Qualcuno può spiegarlo in modo un po ‘più dettagliato? deve fare qualcosa con la serie logaritmica?

Ecco un modo più matematico di vederlo, anche se non è davvero complicato. IMO molto più chiaro di quelli informali:

La domanda è, quante volte puoi dividere N per 2 finché non ne hai 1? Questo essenzialmente sta dicendo, fai una ricerca binaria (metà degli elementi) finché non la trovi. In una formula questo sarebbe questo:

1 = N / 2 x

moltiplicare per 2 x :

2 x = N

ora fai il log 2 :

log 2 (2 x ) = log 2 N
x * log 2 (2) = log 2 N
x * 1 = log 2 N

questo significa che puoi dividere il log N volte finché non hai diviso tutto. Il che significa che devi dividere il log N (“fai il passo di ricerca binario”) finché non trovi il tuo elemento.

Per la ricerca binaria, T (N) = T (N / 2) + O (1) // la relazione di ricorrenza

Applicare il Teorema di Master per calcolare la complessità del tempo di esecuzione delle relazioni di ricorrenza: T (N) = aT (N / b) + f (N)

Qui, a = 1, b = 2 => log (una base b) = 1

inoltre, qui f (N) = n ^ c log ^ k (n) // k = 0 & c = log (una base b)

Quindi, T (N) = O (N ^ c log ^ (k + 1) N) = O (log (N))

Fonte: http://en.wikipedia.org/wiki/Master_theorem

Non fa la metà del tempo di ricerca, che non lo renderebbe log (n). Lo diminuisce logaritmicamente. Pensaci per un momento. Se avessi 128 voci in una tabella e dovessi cercare linearmente il tuo valore, probabilmente occorrerebbero in media circa 64 voci per trovare il tuo valore. È n / 2 o tempo lineare. Con una ricerca binaria, eliminate 1/2 delle voci possibili ciascuna iterazione, tale che al massimo ci vorranno solo 7 confronti per trovare il vostro valore (la base di registro 2 di 128 è 7 o 2 per 7 la potenza è 128.) Questo è il potere della ricerca binaria.

T (n) = T (n / 2) +1

T (n / 2) = T (n / 4) + 1 + 1

Metti il ​​valore di (n / 2) in sopra così T (n) = T (n / 4) + 1 + 1. . . . T (n / 2 ^ k) + 1 + 1 + 1 + 1 …..

= T (2 ^ k / 2 ^ k) + 1 + 1 …. + 1 fino a k

= T (1) + k

Come abbiamo preso 2 ^ k = n

K = registro n

Quindi la complessità del tempo è O (log n)

La complessità temporale dell’algoritmo di ricerca binaria appartiene alla class O (log n). Questa è chiamata notazione O grande . Il modo in cui dovresti interpretare questo è che la crescita asintotica del tempo che la funzione impiega per eseguire un dato set di input di dimensione n non supererà il log n .

Questo è solo un gergo matematico formale per essere in grado di dimostrare affermazioni, ecc. Ha una spiegazione molto semplice. Quando n diventa molto grande, la funzione log n farà crescere il tempo necessario per eseguire la funzione. La dimensione del “set di input”, n, è solo la lunghezza della lista.

In poche parole, il motivo per cui la ricerca binaria è in O (log n) è che dimezza l’input impostato in ciascuna iterazione. È più facile pensarci nella situazione opposta. Su iterazioni x, per quanto tempo l’elenco può esaminare l’algoritmo di ricerca binaria al massimo? La risposta è 2 ^ x. Da questo possiamo vedere che il contrario è che in media l’algoritmo di ricerca binaria necessita di log2 n iterazioni per un elenco di lunghezza n.

Se il motivo per cui è O (log n) e non O (log2 n), è perché semplicemente rimetti – Le costanti di notazione O grande non contano.

Ecco la voce di Wikipedia

Se guardi al semplice approccio iterativo. Stai eliminando solo metà degli elementi da cercare finché non trovi l’elemento di cui hai bisogno.

Ecco la spiegazione di come viene la formula.

Dì inizialmente hai N numero di elementi e quindi quello che fai è ⌊N / 2⌋ come primo tentativo. Dove N è la sum del limite inferiore e del limite superiore. Il primo valore di tempo di N sarebbe uguale a (L + H), dove L è il primo indice (0) e H è l’ultimo indice della lista che stai cercando. Se sei fortunato, l’elemento che cerchi di trovare sarà nel mezzo [ad es. Stai cercando 18 nella lista {16, 17, 18, 19, 20} quindi calcoli ⌊ (0 + 4) / 2⌋ = 2 dove 0 è inferiore (indice L del primo elemento dell’array) e 4 è il limite superiore (indice H dell’ultimo elemento dell’array). Nel caso sopra L = 0 e H = 4. Ora 2 è l’indice dell’elemento 18 che stai cercando trovato. Bingo! L’hai trovato.

Se il caso era un array diverso {15,16,17,18,19} ma stavi ancora cercando 18 allora non saresti fortunato e faresti il ​​primo N / 2 (che è ⌊ (0 + 4) / 2⌋ = 2 e quindi rendi conto che l’elemento 17 nell’indice 2 non è il numero che stai cercando. Ora sai che non devi cercare almeno la metà dell’array nel tuo prossimo tentativo di cercare modalità iterative. lo sforzo di ricerca è dimezzato. Quindi, in pratica, non cerchi la metà dell’elenco di elementi che hai cercato in precedenza, ogni volta che provi a trovare l’elemento che non sei riuscito a trovare nel tuo precedente tentativo.

Quindi il caso peggiore sarebbe

[N] / 2 + [(N / 2)] / 2 + [((N / 2) / 2)] / 2 …..
vale a dire:
N / 2 1 + N / 2 2 + N / 2 3 + ….. + N / 2 x … ..

fino a quando … hai finito di cercare, dove nell’elemento che stai cercando di trovare è alla fine della lista.

Ciò dimostra che il caso peggiore è quando raggiungi N / 2 x dove x è tale che 2 x = N

In altri casi N / 2 x dove x è tale che 2 x

Ora dal punto di vista matematico il caso peggiore è quando il valore di
2 x = N
=> log 2 (2 x ) = log 2 (N)
=> x * log 2 (2) = log 2 (N)
=> x * 1 = log 2 (N)
=> Più formalmente ⌊log 2 (N) + 1⌋

Log2 (n) è il numero massimo di ricerche richieste per trovare qualcosa in una ricerca binaria. Il caso medio coinvolge log2 (n) -1 ricerche. Ecco ulteriori informazioni:

http://en.wikipedia.org/wiki/Binary_search#Performance

Una ricerca binaria funziona dividendo il problema a metà ripetutamente, qualcosa del genere (dettagli omessi):

Esempio alla ricerca di 3 in [4,1,3,8,5]

  1. Ordina il tuo elenco di articoli [1,3,4,5,8]
  2. Guarda l’object centrale (4),
    • Se è quello che stai cercando, fermati
    • Se è più grande, guarda il primo semestre
    • Se è inferiore, guarda la seconda metà
  3. Ripeti il ​​passaggio 2 con il nuovo elenco [1, 3], trova 3 e interrompi

È una ricerca bi- naria quando si divide il problema in 2.

La ricerca richiede solo passi log2 (n) per trovare il valore corretto.

Consiglierei l’ introduzione agli algoritmi se si desidera conoscere la complessità algoritmica.

Dal momento che abbiamo tagliato una lista in metà ogni volta quindi abbiamo solo bisogno di sapere in quanti passi otteniamo 1 mentre dividiamo una lista per due. Nel sotto calcolo x indica il numero di volte in cui divideremo una lista fino a ottenere un elemento (nel peggiore dei casi).

1 = N / 2x

2x = N

Prendendo log2

log2 (2x) = log2 (N)

x * log2 (2) = log2 (N)

x = log2 (N)