Page 19 - REVISTA MATINF Nr. 5

Complexitatea algoritmului de sortare prin interclasare (mergesort) 19

+
Notˆand cu N (n) num˘arul de comparat ,ii de chei ˆın cazul cel mai defavorabil, din (2) s , i (5)
c
rezult˘a relat , ia de recurent , ˘a
(
0, dac˘a n = 1,
+
n
n
N (n) = + l m + j k (6)
c
N
c + N c + n − 1, dac˘a n > 1.
2 2
Rezolv˘am aceast˘a relat , ie de recurent , ˘a.
Pentru n = num˘ar par, adic˘a n = 2m, m ≥ 1, avem
+
+
+
+
N (n + 1) − N (n) = N (2m + 1) − N (2m)
c
c
c
c
+
+
+
+

= N (m + 1) + N (m) + 2m − N (m) + N (m) + 2m − 1
c c c c
+
+
= N (m + 1) − N (m) + 1,
c
c
iar pentru n = num˘ar impar, adic˘a n = 2m − 1, m ≥ 2, avem
+
+
+
+
N (n + 1) − N (n) = N (2m) − N (2m − 1)
c c c c
+
+
+
+

= N (m) + N (m) + 2m − 1 − N (m) + N (m − 1) + 2m − 2
c
c
c
c
+
+
= N (m) − N (m − 1) + 1,
c c
deci pentru orice n > 1 avem
n n
j k j k
+
+
N (n + 1) − N (n) = N c + + 1 − N c + + 1.
c
c
2 2
Notˆand
∗
+
+
f(n) = N (n + 1) − N (n), ∀n ∈ N , (7)
c c
obt , inem c˘a
(
1, dac˘a n = 1,
n
f(n) = j k (8)
f + 1, dac˘a n > 1.
2
Demonstr˘am c˘a
∗
f(n) = dlog (n + 1)e, ∀n ∈ N , (9)
2
prin induct , ie.
Pentru n = 1 avem f(1) = 1 = dlog 2e.
2
Presupunem egalitatea 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 (8) s , i ipoteza de
n
j k
induct , ie pentru avem
2
n n
j k l j k m
f(n) = f + 1 = log 2 + 1 + 1.
2 2
∗
Dar, notˆand dlog (n + 1)e = k, avem k ∈ N , k ≥ 2 s , i, succesiv:
2
k
k − 1 < log (n + 1) ≤ k; 2 k−1 < n + 1 ≤ 2 ;
2
n
k
2 k−1 ≤ n < 2 ; 2 k−2 ≤ < 2 k−1 ;
2
n
n
j k j k
2 k−2 ≤ < 2 k−1 ; 2 k−2 < + 1 ≤ 2 k−1 ;
2 2
n
j k
k − 2 < log + 1 ≤ k − 1;
2
2
n
l j k m
log 2 + 1 = k − 1,
2