Page 45 - MATINF Nr. 3

Complexitatea algoritmilor de sortare 45

arborele extins de sortare asociat are 6 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 4!e 112
2
dlog 4!e + 1 − = = 4,(6).
2
4! 24
∗
Lema 1. Pentru orice n ∈ N au loc inegalit˘at ,ile:
1 1
< ln(n + 1) − ln n < ; (2)
n + 1 n
n log n − (n − 1) log e ≤ log n! ≤ n log n. (3)
2
2
2
2
Demonstrat¸ie. Aplicˆand Teorema lui Lagrange pentru funct , ia f : [n, n + 1] → R, f(x) = ln x
0
(f este derivabil˘a), rezult˘a c˘a exist˘a c ∈ (n, n + 1) a.ˆı. f(n + 1) − f(n) = f (c), adic˘a
1 1 1 1
ln(n + 1) − ln n = . Dar < < , deci obt , inem relat , ia (2).
c n + 1 c n
Din aceast˘a relat , ie rezult˘a c˘a (n + 1) ln(n + 1) − n ln n < 1 + ln(n + 1), deci
2 ln 2 − ln 1 < 1 + ln 2,

3 ln 3 − 2 ln 2 < 1 + ln 3,
. . .
n ln n − (n − 1) ln(n − 1) < 1 + ln n.

Prin adunare obt , inem c˘a
n ln n < n − 1 + ln n!, ∀ n ≥ 2,

de unde, utilizˆand formula log x = log e · ln x, ∀x > 0, rezult˘a prima inegalitate din (3),
2
2
valabil˘a s , i pentru n = 1. A doua inegalitate din (3) este o consecint , ˘a a inegalit˘at , ii evidente
n
n! ≤ n .
Lema 2. Funct ,iile log n! s , i n log n sunt asimptotic echivalente, adic˘a
2 2
log n! ∼ n log n.
2
2
Demonstrat¸ie. Din (3) rezult˘a c˘a
(n − 1) log e log n!
∗
1 − 2 ≤ 2 ≤ 1, ∀ n ∈ N ,
n log n n log n
2 2
log n!
deci aplicˆand Criteriul cles , telui avem lim 2 = 1, adic˘a log n! ∼ n log n.
2
2
n→∞ n log n
2
2 dlog n!e
2
Lema 3. Avem dlog n!e + 1 − ∼ n log n.
2
2
n!
Demonstrat¸ie. Cum log n! ≤ dlog n!e < 1 + log n!, rezult˘a c˘a n! ≤ 2 dlog n!e < 2 · n!, adic˘a
2
2 2 2
n! ≤ 2 dlog n!e ≤ 2 · n! − 1, deci
2
1 2 dlog n!e
2
log n! − 1 + ≤ dlog n!e + 1 − < log n! + 1.
2
2
2
n! n!
2 dlog n!e
2
dlog n!e + 1 −
2
Aplicˆand Criteriul cles , telui obt , inem lim n! = 1, deci folosind lema anteri-
n→∞ log n!
2
2 dlog n!e
2
dlog n!e + 1 −
2
oar˘a rezult˘a c˘a lim n! = 1, adic˘a echivalent , a asimptotic˘a din enunt , .
n→∞ n log n
2