Page 24 - REVISTA MATINF Nr. 5

24 C. B˘alc˘au

(deoarece dxe ≥ x, dye ≥ y, dxe + dye ≥ x + y s , i dxe + dye ∈ Z, deci dxe + dye = ddxe + dyee ≥
dx + ye ). Folosind (19) rezult˘a c˘a

+
N (n) = dlog 1e + dlog 2e + . . . + dlog ne ≥ dlog 1 + log 2 + . . . + log ne = N def (n),
c 2 2 2 2 2 2
+
ceea ce era de as , teptat, conform optimalit˘at , ii invocate! Mai mult, avem N (5) = dlog 1e +
c 2
dlog 2e + dlog 3e + dlog 4e + dlog 5e = 0 + 1 + 2 + 2 + 3 = 8, iar N def (5) = dlog 5!e =
2
2
2
2
2
dlog 120e = 7, deci
2
+
N (5) > N def (5).
c
Folosind aceast˘a inegalitate strict˘a s , i inegalitatea (19), rezult˘a c˘a pentru n ≥ 5 avem
+
N (n) = (dlog 1e + . . . + dlog 5e) + (dlog 6e + . . . + dlog ne)
2
2
2
2
c
> dlog 1 + . . . + log 5e + dlog 6 + . . . + log ne
2 2 2 2
≥ dlog 1 + . . . + log 5 + log 6 + . . . + log ne = N def (n),
2
2
2
2
deci
+
N (n) > N def (n), ∀ n ≥ 5.
c
Prin urmare algoritmul mergesort nu este optim ˆın raport cu timpul de execut , ie ˆın cazul cel
mai defavorabil. Cum, conform Corolarului 1 din [3], optimalitatea ˆın cazul timpului mediu de
execut , ie implic˘a optimalitatea ˆın cazul cel mai defavorabil, rezult˘a c˘a algoritmul mergesort nu
este optim nici ˆın raport cu timpul mediu de execut , ie.
Observat ,ia 5. Complexitatea algoritmului mergesort este una dintre cele mai bune din punct de
vedere al num˘arului de comparat , ii de chei, ˆın clasa algoritmilor de sortare bazat , i pe astfel de
comparat , ii. Un dezavantaj este ˆıns˘a faptul c˘a se utilizeaz˘a un vector suplimentar de lucru, care
poate avea dimensiunea foarte mare (fiind egal˘a cu cea a vectorului ce trebuie sortat).
Bibliografie

[1] Gh. Barbu, I. V˘aduva, M. Bolos , teanu, Bazele informaticii, Editura Tehnic˘a, Bucures , ti, 1997.

[2] C. B˘alc˘au, Optimalitatea algoritmului de c˘autare binar˘a, MATINF I (2018), nr. 1, 39–51.

[3] C. B˘alc˘au, Complexitatea algoritmilor de sortare, MATINF II (2019), nr. 3, 41–48.

[4] A. Carabineanu, Structuri de date, http://ebooks.unibuc.ro/informatica/carabineanu/CARA_
STR.pdf.
[5] T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, MIT Press,
Cambridge, 2009.

[6] H. Georgescu, Tehnici de programare, Editura Universit˘at , ii din Bucures , ti, Bucures , ti, 2005.

[7] D.E. Knuth, The Art Of Computer Programming. Vol. 3: Sorting and Searching, Addison-
Wesley, Reading, MA, 1998.

[8] R. Sedgewick, P. Flajolet, An Introduction to the Analysis of Algorithms, Addison-Wesley,
New Jersey, 2013.

[9] R. Sedgewick, K. Wayne, Algorithms, Addison-Wesley, Massachusetts, 2011.