If you're seeing this message, it means we're having trouble loading external resources on our website.

Dacă sunteţi în spatele unui filtru de web, vă rugăm să vă asiguraţi că domeniile *. kastatic.org şi *. kasandbox.org sunt deblocate.

Conţinutul principal

Timpul de execuție al căutării binare

Știm că, pe un vector de n elemente, căutarea liniară ar putea avea nevoie de n încercări. Probabil ai intuit deja că prin căutarea binară se fac mai puţine încercări decât prin căutarea liniară. S-ar putea să fi înțeles că diferența dintre cel mai defavorabil caz pentru căutarea liniară și căutarea binară devine tot mai frapantă pe măsură ce lungimea vectorului crește. Să vedem cum analizăm numărul maxim de încercări pe care le facem cu căutarea binară.
Ideea cheie este că atunci când căutarea binară face o încercare incorectă, lungimea vectorului care conține valori rezonabile este redusă cu cel puțin jumătate. Dacă vectorul inițial are 32 de elemente, atunci o încercare incorectă îl va reduce la cel mult 16 elemente. Căutarea binară înjumătățește numărul valorilor rezonabile la fiecare încercare incorectă.
Dacă începem cu un vector de lungime 8, atunci încercările incorecte reduc numărul valorilor rezonabile la 4, apoi la 2, iar apoi la 1. Odată ce avem un singur element rezonabil, nu se mai fac alte încercări; încercarea pentru 1 element este fie corectă, fie incorectă, apoi am terminat. Deci pentru un vector de lungime 8, căutarea binară are nevoie de cel mult patru încercări.
Ce crezi că se întâmplă cu un vector de 16 elemente? Dacă ai spus că prima încercare ar elimina cel puțin 8 elemente, astfel încât cel mult 8 să rămână, înseamnă că ai înțeles ideea. Deci, pentru 16 elemente avem nevoie de cel mult cinci încercări.
De acum, probabil vezi șablonul. De fiecare dată când dublăm dimensiunea vectorului, avem nevoie de cel mult încă o încercare. Presupunem că avem nevoie de cel mult m încercări pentru un vector de n elemente. Apoi, pentru un vector de lungime 2n, prima încercare elimină din valorile rezonabile din vector până la un număr de n valori, iar după cel mult m încercări se termină, dându-ne un total de cel mult m+1 încercări.
Să ne uităm la cazul general al unui vector de lungime n. Am putea exprima numărul de încercări, în cel mai defavorabil caz, astfel: "de câte ori putem înjumătăți, începând cu n, până când obținem valoarea 1, plus unu". Dar nu e convenabil să scriem așa.
Din fericire, există o funcţie matematică care înseamnă acelaşi lucru cu numărul înjumătățiri, începând de la n, până când pajungem la valoarea 1: logaritm în baza 2 din n. Este cel mai adesea scris ca log2n, dar îl poți întâlni și scris ca lgn, în scrierile din informatică. Vrei să recapitulezi logaritmii? Află mai multe aici.)
Iată un tabel care conține logaritmii în baza 2 pentru diverse valori ale lui n:
nlog2n
10
21
42
83
164
325
646
1287
2568
5129
102410
1.048.57620
2.097.15221
Putem vedea același tabel ca un grafic:
Evidențierea pentru valori mai mici ale lui n:
Funcția logaritm crește foarte lent. Logaritmii sunt funcții inverse ale exponentialelor, care cresc foarte rapid, astfel încât dacă log2n=x, atunci n=2x. De exemplu, deoarece log2128=7, avem 27=128.
Acest lucru face ușoară calcularea timpului de execuție a unui algoritm de căutare binară pentru un n care este exact o putere de 2. Dacă n este 128, căutarea binară va necesita cel mult 8 (log2128+1) încercări.
Ce se întâmplă dacă n nu este o putere de 2? În acest caz, ne putem uita la cea mai apropiată putere a lui 2 mai mică decât numărul respectiv. Pentru un vector a cărui lungime este 1000, cea mai apropiată putere a lui 2 mai mică decât 1000 este 512, ceea ce înseamnă 29. Astfel, putem estima că log21000 este un număr mai mare de 9 și mai mic de 10, sau folosim un calculator pentru a vedea că este aproximativ 9,7. Adunând unu la această valoare rezultă aproximativ 10.7. În cazul unei zecimale, rotunjim prin lipsă pentru a găsi numărul real de încercări. Prin urmare, pentru un vector cu 1000 de elemente, ar fi necesară o căutare binară cu cel mult 10 încercări.
Pentru catalogul de stele Tycho-2, cu 2.539.913 stele, cea mai apropiată putere a lui 2 mai mică este 221 (adică 2.097.152), așa că am avea nevoie de cel mult 22 de încercări. Mult mai bine decât căutarea liniară!
Mai jos, comparăm n cu log2n:
În următorul tutorial, vom vedea cum oamenii de știință din informatică caracterizează timpul de execuție pentru căutarea liniară și pentru căutarea binară, utilizând o notație care ține cont de cea mai importantă parte a timpului de execuție și renunță la părțile mai puțin importante.
Acest conținut este o colaborare a profesorilor Thomas Cormen și Devin Balkcom, de la Dartmouth Computer Science, cu echipa de elaborare a curriculumului de informatică de la Khan Academy. Conținutul este licențiat CC-BY-NC-SA.