Page 44 - MATINF Nr. 3

44 C. B˘alc˘au

strict T cu p noduri interne avem

X dlog (p+1)e
D T (v) ≥ (p + 1) dlog (p + 1)e + p + 1 − 2 2 . (1)
2
v∈E(T)

n! dlog n!e + n! − 2 dlog n!e 2 dlog n!e
2
2
Rezult˘a c˘a N med (n) ≥ 2 = dlog n!e + 1 − .
n! 2 n!
Corolarul 1. Fie A un algoritm de sortare, bazat pe comparat ,ii de chei, a unui vector cu n
componente s , i fie T = T (A) arborele extins de sortare asociat.

1) Algoritmul A este optim ˆın raport cu timpul de execut ,ie ˆın cazul cel mai defavorabil dac˘a
arborele T are toate nodurile externe situate pe ultimul s , i, eventual, pe penultimul nivel. Mai
mult, ˆın acest caz num˘arul de comparat ,ii de chei efectuate ˆın cazul cel mai defavorabil, notat cu
N def (n), verific˘a egalitatea
N def (n) = dlog n!e .
2

2) Algoritmul A este optim ˆın raport cu timpul mediu de execut ,ie dac˘a s , i numai dac˘a arborele
T are toate nodurile externe situate pe ultimul s , i, eventual, pe penultimul nivel. Mai mult, ˆın
acest caz num˘arul mediu de comparat ,ii de chei efectuate, notat cu N med (n), verific˘a egalitatea

2 dlog n!e
2
N med (n) = dlog n!e + 1 − .
2
n!
Demonstrat¸ie. Optimalitatea ˆın raport cu timpul de execut , ie ˆın cazul cel mai defavorabil este
o consecint , ˘a direct˘a a Cazului 1 din propozit , ia anterioar˘a s , i a Propozit , iei 5 din [2], conform
c˘areia orice arbore binar strict T cu p noduri interne s , i cu toate nodurile externe situate pe
ultimul s , i, eventual, pe penultimul nivel are ˆın˘alt , imea h(T) = dlog (p + 1)e.
2
Optimalitatea ˆın raport cu timpul mediu de execut , ie este o consecint , ˘a direct˘a a Cazului
2 din propozit , ia anterioar˘a s , i a Propozit , iei 6 din [2], conform c˘areia inegalitatea (1) devine
egalitate dac˘a s , i numai dac˘a arborele T are toate nodurile externe situate pe ultimul s , i, eventual,
pe penultimul nivel.

Exemplul 5. Un algoritm de sortare, bazat pe comparat , ii de chei, a unui vector cu n = 3
componente este optim ˆın raport cu timpul de execut , ie ˆın cazul cel mai defavorabil dac˘a s , i
numai dac˘a ˆın acest caz num˘arul de comparat , ii de chei efectuate este dlog 3!e = 3, adic˘a dac˘a
2
s , i numai dac˘a arborele extins de sortare asociat are 4 nivele.
Pe de alt˘a parte, un algoritm de sortare, bazat pe comparat , ii de chei, a unui vector cu
n = 3 componente este optim ˆın raport cu timpul mediu de execut , ie dac˘a s , i numai dac˘a
arborele extins de sortare asociat are 4 nivele s , i toate nodurile externe situate pe ultimele
dou˘a nivele. Mai mult, ˆın acest caz num˘arul mediu de comparat , ii de chei efectuate este
2 dlog 3!e 16
2
dlog 3!e + 1 − = = 2,(6).
2
3! 6
Analog, un algoritm de sortare, bazat pe comparat , ii de chei, a unui vector cu n = 4
componente este optim ˆın raport cu timpul de execut , ie ˆın cazul cel mai defavorabil dac˘a s , i
numai dac˘a ˆın acest caz num˘arul de comparat , ii de chei efectuate este dlog 4!e = 5, adic˘a dac˘a
2
s , i numai dac˘a arborele extins de sortare asociat are 6 nivele.

Pe de alt˘a parte, un algoritm de sortare, bazat pe comparat , ii de chei, a unui vector cu
n = 4 componente este optim ˆın raport cu timpul mediu de execut , ie dac˘a s , i numai dac˘a