Page 22 - REVISTA MATINF Nr. 5
P. 22

22                                                                                     C. B˘alc˘au



                                            −
                                               t
                    −
            Cum N (1) = 0 obt , inem c˘a N (2 ) − t · 2 t−1  = 0, deci
                    c
                                            c
                                                  −
                                                     t
                                               N (2 ) = t · 2 t−1 , ∀t ∈ N.                              (15)
                                                 c
            Din (14), (15) s , i (13) rezult˘a c˘a ˆın cazul cel mai favorabil num˘arul de comparat ,ii de chei verific˘a
            inegalit˘at , ile
                                                              1             1
                                −
                                                                                          ∗
                              N (n) ≥ blog nc · 2  blog nc−1  >  · n log n −  · n, ∀n ∈ N .              (16)
                                                      2
                                c
                                                                      2
                                            2
                                                              4             4
            Din (11) s , i (16) rezult˘a c˘a num˘arul de comparat ,ii de chei verific˘a inegalit˘at , ile
                                  1             1
                                                                                      ∗
                                    · n log n −   · n < N c (n) < n log n + 1, ∀n ∈ N .                  (17)
                                  4       2     4                     2
                Din relat , iile (3) s , i (4) rezult˘a c˘a num˘arul de deplas˘ari efectuate de algoritm verific˘a relat , ia
            de recurent , ˘a
                                         (
                                                          0,                dac˘a n = 1,
                                                                n
                                                  n
                                N d (n) =      l m         j k
                                            N d        + N d        + 2n, dac˘a n > 1.
                                                  2             2
            Aceast˘a relat , ie se rezolv˘a analog relat , iei (6), obt , inˆandu-se
                                               €                        Š
                                                                                   ∗
                                     N d (n) = 2 ndlog ne − 2 dlog ne  + n , ∀n ∈ N ,
                                                                 2
                                                      2
            deci
                                                                                     ∗
                                   2n log n − 2n < N d (n) < 2n log n + 2n, ∀n ∈ N .                     (18)
                                                                   2
                                         2
                Din relat , iile (1), (17) s , i (18) rezult˘a c˘a T(n) = Θ(n log n).
                                                                        2
                Metoda 2) Vom aplica Teorema Master.          Conform descrierii recursive a algoritmului
                                                                                                n     n
                                                                                             l m j k
            s , i utilizˆand complexitatea procedurii de interclasare (formulele pentru N c        ,       s , i
                                                                                                2     2
                   n     n
                l m j k
            N d       ,      ), timpul de execut , ie T(n) verific˘a relat , ia de recurent , ˘a
                   2     2
                                           T(n) = 2T(n/2) + Θ(n), ∀ n > 1,
            cu convent , iile de notat , ie din Teorema Master (Teorema 1 din [2]). Conform Cazului 2 al acelei
            teoreme (pentru a = 2, b = 2, c = 1 = log a s , i k = 0) rezult˘a c˘a T(n) = Θ(n log n).
                                                                                               2
                                                       b
                Urm˘atorul rezultat este o consecint , ˘a direct˘a a teoremei anterioare s , i a Teoremei 1 din [3]
            (care afirm˘a c˘a orice algoritm optim de sortare, bazat pe comparat , ii de chei, are complexitatea
            Θ(n log n)).
                    2
            Corolarul 4 (optimalitatea algoritmului de sortare prin interclasare). Algoritmul de
            sortare prin interclasare este asimptotic-optim (ˆın clasa algoritmilor bazat ,i pe comparat ,ii de
            chei), atˆat ˆın raport cu timpul de execut ,ie ˆın cazul cel mai defavorabil, cˆat s , i ˆın raport cu timpul
            mediu de execut ,ie.

            Observat ,ia 3. Mai mult, conform relat , iilor (11) s , i (17) s , i Teoremei 1 din [3] rezult˘a c˘a, exact
            ca la algoritmii optimi de sortare bazat , i pe comparat , ii de chei, num˘arul de comparat , ii de chei
            efectuate de algoritmul de sortare prin interclasare a unui vector cu n componente este chiar
            asimptotic echivalent cu n log n, atˆat ˆın cazul cel mai defavorabil, cˆat s , i ˆın cazul mediu (cazul
                                          2
            timpului mediu de execut , ie).
   17   18   19   20   21   22   23   24   25   26   27