Page 21 - REVISTA MATINF Nr. 5
P. 21
Complexitatea algoritmului de sortare prin interclasare (mergesort) 21
Astfel rezult˘a c˘a ˆın cazul cel mai defavorabil num˘arul de comparat ,ii de chei verific˘a inegalit˘at , ile
∗
+
n log n − 2n + 1 < N (n) < n log n + 1, ∀n ∈ N . (11)
2 c 2
−
Notˆand cu N (n) num˘arul de comparat ,ii de chei ˆın cazul cel mai favorabil, din (2) s , i (5)
c
rezult˘a relat , ia de recurent , ˘a
(
0, dac˘a n = 1,
−
n
n
n
N (n) = l m j k j k (12)
c N − + N − + , dac˘a n > 1.
c c
2 2 2
−
Demonstr˘am c˘a s , irul (N (n)) n≥1 este cresc˘ator, adic˘a
c
−
∗
−
N (n + 1) ≥ N (n), ∀ n ∈ N ,
c c
prin induct , ie.
−
−
Pentru n = 1 avem N (2) = 1 > 0 = N (1).
c
c
Presupunem inegalitatea adev˘arat˘a pentru orice num˘ar din mult , imea {1, . . . , n − 1} s , i o
ˆ
demonstr˘am pentru n (n ≥ 2). Intr-adev˘ar, folosind relat , ia de recurent , ˘a (12), ipoteza de induct , ie
n n
l m j k
pentru cˆand n este par, respectiv pentru cˆand n este impar, precum s , i inegalitatea
2 2
j k
n + 1 n
evident˘a ≥ , avem
2 2
¡ n + 1 ¤ n + 1 n + 1
−
N (n + 1) = N c − + N c − +
c
2 2 2
n n n
l m j k j k
≥ N c − + N c − +
2 2 2
−
= N (n).
c
Demonstrat , ia prin induct , ie este ˆıncheiat˘a.
∗
Fie n ∈ N s , i
t = blog nc, (13)
2
−
t
deci t ∈ N s , i t ≤ log n < t + 1, deci 2 ≤ n < 2 t+1 . Deoarece s , irul (N (n)) n≥1 este cresc˘ator,
2
c
rezult˘a c˘a
−
−
t
N (n) ≥ N (2 ). (14)
c
c
Dar, conform relat , iei de recurent , ˘a (12) avem
∗
−
−
t
N (2 ) = 2N (2 t−1 ) + 2 t−1 , ∀ t ∈ N .
c
c
Rescriem aceast˘a egalitate sub forma
∗
t
−
−
N (2 ) − t · 2 t−1 = 2 N (2 t−1 ) − (t − 1)2 t−2 , ∀ t ∈ N ,
c c
Aplicˆand succesiv aceast˘a relat , ie avem
−
−
t
N (2 ) − t · 2 t−1 = 2 N (2 t−1 ) − (t − 1)2 t−2
c c
−
= 2 2 N (2 t−2 ) − (t − 2)2 t−3
c
. . .
t
−
= 2 N (2 t−t ) − (t − t)2 t−t−1
c
