Page 18 - REVISTA MATINF Nr. 5
P. 18

18                                                                                     C. B˘alc˘au



                Metoda 1) Vom estima efectiv timpul de execut , ie T(n). Vom num˘ara numai operat , iile de
            comparat , ie de chei (comparat , ii ˆın care intervin elemente ale vectorului) s , i de deplas˘ari
            (atribuiri ˆın care intervin elemente ale vectorului). Celelalte operat , ii care se efectueaz˘a au acelas , i
            ordin de cres , tere cu cele pe care le analiz˘am. Avem

                                             T(n) = c 1 · N c (n) + c 2 · N d (n),                        (1)


            unde N c (n) s , i N d (n) reprezint˘a num˘arul de comparat ,ii de chei, respectiv num˘arul de deplas˘ari
            efectuate de algoritm, iar c 1 , c 2 > 0 sunt constante ce reprezint˘a costurile ˆın timp ale execut˘arii
            unei comparat ,ii de chei s , i, respectiv, ale unei deplas˘ari.

                Conform descrierii recursive a algoritmului, rezult˘a c˘a numerele N c (n) s , i N d (n) verific˘a,
            respectiv, relat , iile de recurent , ˘a

                                  (
                                                          0,                       dac˘a n = 1,
                                           n
                                                                            n
                                                                      n
                                                        n
                         N c (n) =      l m        j k         l m j k                              (2)
                                     N c        + N c        + N c       ,      , dac˘a n > 1,
                                           2            2             2     2
                                  (
                                                          0,                       dac˘a n = 1,
                                           n
                                                        n
                                                                            n
                                                                      n
                         N d (n) =      l m        j k         l m j k                              (3)
                                     N d        + N d        + N d       ,       , dac˘a n > 1,
                                           2             2            2     2
                        n     n             n     n
                      l m j k          l m j k
            unde N c        ,      s , i N d    ,      reprezint˘a num˘arul de comparat ,ii de chei, respectiv
                         2    2             2     2
            num˘arul de deplas˘ari efectuate la interclasarea celor doi subvectori sortat , i, (a 1 , . . . , a m ) s , i
                                    ›      ž
                                      n + 1     l m                      l m                          l m
                                                                                                       n
                                                 n
                                                                           n
            (a m+1 , . . . , a n ), cu m =   =      , de dimensiuni m =       , respectiv n − m = n −      =
                                        2        2                         2                           2
              n
            j k
                 .
              2
                Conform descrierii procedurii de interclasare, la interclasarea celor doi subvectorilor avem:
                                                n     n
                                             l m j k
                • Num˘arul de deplas˘ari N d        ,      este egal cu dublul num˘arul de componente ale
                                                2     2
                  lui A (fiecare component˘a - fie c˘a se afl˘a ˆın primul subvector, fie c˘a se afl˘a ˆın al doilea
                  subvector - este mutat˘a o dat˘a ˆın vectorul intermediar B s , i o dat˘a adus˘a ˆınapoi ˆın A),
                  deci
                                                 n     n           n      n
                                              l m j k         l m    j k
                                          N d       ,       = 2       +        = 2n.                      (4)
                                                 2     2           2      2
                                                           n     n
                                                        l m j k
                • Num˘arul de comparat ,ii de chei N c        ,       este egal cu num˘arul de execut , ii ale
                                                           2     2
                  ciclului while. Cu fiecare astfel de comparat , ie are loc s , i o copiere ˆın vectorul B a unei
                  componente din A, adic˘a o deplasare. La ies , irea din ciclul while, componentele unuia
                  dintre cei doi subvectori ai lui A au fost toate copiate ˆın B, iar ˆın cel˘alalt subvector au
                  mai r˘amas r componente necopiate ˆın B, care vor fi s , i ele copiate ˆın B, dar dup˘a ies , irea
                  din acest ciclu. Rezult˘a c˘a
                                                         n     n
                                                      l m j k
                                                   N c      ,       = n − r.
                                                         2     2
                  Evident,
                                                              n     n        n
                                                           nl m j ko        l m
                                              1 ≤ r ≤ max         ,      =       ,
                                                              2     2        2
                  deci
                                             n     n          n    n
                                          l m j k        nj k j k                  o
                                       N c       ,      ∈        ,     + 1, . . . , n − 1 .               (5)
                                              2    2          2     2
   13   14   15   16   17   18   19   20   21   22   23