Page 51 - MATINF Nr. 1
P. 51
Optimalitatea algoritmului de c˘autare binar˘a 51
n
Evident, log n − 1 < blog nc ≤ log n, deci < 2 blog nb ≤ n. Rezult˘a c˘a
2
2
2
2
2
3n − 2 − log n n + 4 + log n
log n − 2 < T(n) < log n + 2 , deci
2
2
2n + 1 2n + 1
3n − 2 − log n T(n) n + 4 + log n
1 − 2 < < 1 + 2 , ∀ n ≥ 2.
(2n + 1) log n log n (2n + 1) log n
2
2
2
Aplicˆand Criteriul cles , telui rezult˘a c˘a
T(n)
lim = 1, (7)
n→∞ log n
2
deci conform Propozit , iei 1 obt , inem c˘a T(n) = Θ(log n).
2
Mai mult, conform relat , iei (7) am obt , inut urm˘atorul rezultat.
Corolarul 2. Num˘arul mediu de comparat ,ii de chei efectuate de algoritmul de c˘autare binar˘a
ˆıntr-un vector sortat cu n componente este asimptotic echivalent cu log n.
2
Teorema 4 (optimalitatea algoritmului de c˘autare binar˘a). Algoritmul de c˘autare binar˘a
este optim (ˆın clasa algoritmilor bazat ,i pe comparat ,ii de chei), atˆat ˆın raport cu timpul de execut ,ie
ˆın cazul cel mai defavorabil, cˆat s , i ˆın raport cu timpul mediu de execut ,ie.
Demonstrat¸ie. Optimalitatea ˆın raport cu timpul de execut , ie ˆın cazul cel mai defavorabil este o
consecint , ˘a direct˘a a Propozit , iei 7 s , i a primei p˘art , i din Teorema 2. Optimalitatea ˆın raport cu
timpul mediu de execut , ie este o consecint , ˘a direct˘a a relat , iei (6) din demonstrat , ia Teoremei 3 s , i
a p˘art , ii secunde din Teorema 2.
Bibliografie
[1] Gh. Barbu, I. V˘aduva, M. Bolos , teanu, Bazele informaticii, Editura Tehnic˘a, Bucures , ti, 1997.
[2] A. Carabineanu, Structuri de date, http://ebooks.unibuc.ro/informatica/carabineanu/CARA STR.pdf.
[3] T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, MIT Press,
Cambridge, 2009.
[4] H. Georgescu, Tehnici de programare, Editura Universit˘at , ii din Bucures , ti, Bucures , ti, 2005.
[5] D.E. Knuth, The Art Of Computer Programming. Vol. 4A: Combinatorial Algorithms,
Addison-Wesley, Massachusetts, 2011.
[6] R. Sedgewick, P. Flajolet, An Introduction to the Analysis of Algorithms, Addison-Wesley,
New Jersey, 2013.
