[Teoria złożoności] Sortowanie przez wstawianie

[nowik1991]

Witam Mam za zdanie obliczyć koszt podanego "Insertion Sort" czyli sortowanie przez wstawianie:

Kod: Zaznacz cały

void InsertionSort(const int* aTablica, unsigned uRozmiar)

{

 
 for (i = 1;                                // [tex]1[/tex]
        i < uRozmiar;                           // [tex]n[/tex]

        ++i)                                      // [tex]n - 1[/tex]

   {

         nElement = aTablica[i];                  // [tex]n - 1[/tex]

 

         for (j = i - 1;                          // [tex]n -1[/tex]

              i >= 0 && aTablica[j] > nElement;   // [tex]sum_{i=2}^{n}  t_{i}[/tex]

              --j)                                // [tex]sum_{i=2}^{n}  (t_{i}-1)[/tex] 

               aTablica[j + 1] = aTablica[j];     //[tex]sum_{i=2}^{n}  (t_{i}-1)[/tex] 

 

         aTablica[j + 1] = nElement;              // [tex]n - 1[/tex]

   }

}

Ok zatem policzmy koszt sumaryczny naszego problemu

Pierwsza pętla:

\(\displaystyle{ (1+n+n-1) = (2n+1-1)=2n}\) Zatem jej koszt jest równy 2n.

Teraz dodajmy to:

Kod: Zaznacz cały

nElement = aTablica[i];

czyli \(\displaystyle{ 2n+n-1=3n-1}\)

Ok to teraz liczymy koszt pętli wewnętrznej:

\(\displaystyle{ ((n-1)+\sum_{i=2}^{n} t_{i}+\sum_{i=2}^{n} (t_{i}-1)) = ((n-1)+\sum_{i=2}^{n} t_{i}-\sum_{i=2}^{n} (t_{i}) = n-1}\)

Teraz dodajemy

Kod: Zaznacz cały

aTablica[j + 1] = aTablica[j]; 

to kosztuje nas \(\displaystyle{ \sum_{i=2}^{n} (t_{i}-1)}\)

\(\displaystyle{ (n-1)+\sum_{i=2}^{n} (t_{i}-1)= n-2\sum_{i=2}^{n} t_{i}}\)

I koszt ostatniego przypisania: \(\displaystyle{ (n-1)}\)

Ok to teraz sumujmy to wszystko:

\(\displaystyle{ T(n)=3n-1+n-1+n-2\sum_{i=2}^{n} t_{i}= 5n-2 -2\sum_{i=2}^{n} t_{i}}\) Mi właśnie wyszedł taki wynik a niby poprawny jest taki:

\(\displaystyle{ T(n)=4n-2+2\sum_{i=2}^{n} t_{i}}\) proszę o pomoc i ewentualną poprawę...