Page 43 - MATINF Nr. 3

Complexitatea algoritmilor de sortare 43

Exemplul 4. Arborele extins de sortare asociat algoritmului de sortare prin insert , ie direct˘a
pentru n = 3 este reprezentat ˆın figura urm˘atoare.

1?2

≤ >

2?3 1?3
≤ > ≤ >

(1,2,3) 1?3 (2,1,3) 2?3

≤ > ≤ >

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

Propozit , ia 1. Pentru orice algoritm de sortare A, bazat pe comparat ,ii de chei, a unui vector
cu n componente avem:

1) num˘arul de comparat ,ii de chei efectuate ˆın cazul cel mai defavorabil, notat cu N def (n),
verific˘a inegalitatea
N def (n) ≥ dlog n!e
2
(dxe reprezint˘a aproximarea ˆıntreag˘a prin adaos a num˘arului real x, numit˘a s , i partea ˆıntreag˘a
superioar˘a a lui x);
2) num˘arul mediu de comparat ,ii de chei efectuate, notat cu N med (n), verific˘a inegalitatea

2 dlog n!e
2
N med (n) ≥ dlog n!e + 1 − .
2
n!
Demonstrat¸ie. Cazul 1) Analiz˘am cazul cel mai defavorabil.

Evident, num˘arul de comparat , ii de chei efectuate ˆın cazul cel mai defavorabil este egal cu
ˆın˘alt , imea h a arborelui extins de sortare asociat T = T (A).

Arborele T este un arbore binar strict, cu n! − 1 noduri interne (s , i n! noduri externe). Dar,
conform Propozit , iei 4 din [2], orice arbore binar strict T cu p noduri interne s , i ˆın˘alt , imea h(T)
verific˘a h(T) ≥ dlog (p + 1)e. Rezult˘a c˘a h ≥ dlog n!e .
2 2
Cazul 2) Analiz˘am acum cazul mediu (cazul timpului mediu de execut , ie).

Pentru fiecare din cele n! permut˘ari σ ale mult , imii de indici {1, 2, . . . , n}, num˘arul de
comparat , ii de chei efectuate de algoritmul A ˆın cazul ordinii a σ(1) ≤ a σ(2) ≤ . . . ≤ a σ(n) este egal
cu distant , a de la r˘ad˘acina arborelui extins de sortare asociat la nodul extern etichetat cu σ.
Deci num˘arul mediu de comparat , ii de chei are valoarea

P
D(k)
k∈E
N med (n) = ,
n!
unde E este mult , imea nodurilor externe, iar, pentru fiecare nod k, D(k) reprezint˘a distant , a de
la r˘ad˘acina arborelui la nodul k. Dar, conform Propozit , iei 6 din [2], pentru orice arbore binar