Page 46 - MATINF Nr. 3

46 C. B˘alc˘au

Urm˘atorul rezultat este o consecint , ˘a imediat˘a a Corolarului 1, Lemelor 2 s , i 3 s , i Corolarului
1 din [2] (conform c˘aruia dac˘a f(n) ∼ g(n), atunci f(n) = Θ(g(n))).

Teorema 1 (complexitatea algoritmilor de sortare). Num˘arul de comparat ,ii de chei
efectuate de un algoritm optim de sortare a unui vector cu n componente este asimptotic
echivalent cu
n log n,
2
atˆat ˆın cazul cel mai defavorabil, cˆat s , i ˆın cazul mediu (cazul timpului mediu de execut ,ie), deci
ˆın ambele cazuri un astfel de algoritm are complexitatea

Θ(n log n).
2
Observat ,ia 4. Dac˘a un algoritm de sortare are instruct , iuni redundante, atunci ˆın arborele extins
de sortare asociat orice nod extern care nu corespunde unei ordini a σ(1) ≤ a σ(2) ≤ . . . ≤ a σ(n)
(calea de la r˘ad˘acin˘a la el fiind imposibil˘a la executarea algoritmului) este etichetat cu Ø.
ˆ
In acest caz arborele extins de sortare va cont , ine mai mult de n! noduri externe (iar arborele
de sortare va cont , ine mai mult de n! − 1 noduri), deci un astfel de algoritm nu poate fi optim ˆın
raport cu timpul mediu de execut , ie.

Exemplul 6. Consider˘am algoritmul de sortare prin select , ie:

SORTSEL(A, n) :
for i = 1, n − 1 do
m ← i; // a m = min{a i , a i+1 , . . . , a n }
for j = i + 1, n do
if A[j] < A[m] then
m ← j;

A[i] ↔ A[m]; // interschimbare

Arborele extins de sortare asociat algoritmului pentru n = 3 este reprezentat ˆın figura
urm˘atoare.

1?2

≤ >

1?3 2?3
≤ > ≤ >

2?3 1?2 1?3 1?2
≤ > ≤ > ≤ > ≤ >

(1,2,3) (1,3,2) (3,1,2) Ø (2,1,3) (2,3,1) Ø (3,2,1)

Observ˘am c˘a algoritmul cont , ine instruct , iuni redundante, s , i anume comparat , ia ˆıntre elemen-
tele a 1 s , i a 2 se efectueaz˘a inutil de dou˘a ori pe penultimul nivel.