Scal złożoność czasu

Podział liczb całkowitych przez dwa

Podział liczb całkowitych jest konieczny podczas scalania.

Gdy liczba nieparzysty jest podzielona przez dwa, pozostała część 1. Na przykład:

7 /2 = 3 R 1

Podział liczb całkowitych oznacza przyjmowanie całkowitej liczby jako odpowiedzi i porzucenia 1.

Gdy liczba równa jest podzielona przez dwa, pozostała część 0. Na przykład:

6 /2 = 3 r 0

Podział liczb całkowitych oznacza przyjmowanie całkowitej liczby jako odpowiedzi i porzucenia 0.

W obu przypadkach liczba całkowita jest przyjmowana, a reszta jest porzucona.

Celem tego artykułu jest określenie złożoności czasu scalania, napisanego również jako scalanie. Sortowanie może być rosnące lub zstępujące. Sortowanie w tym artykule odnosi się do sortowania rosnącego.

Scal algorytm sortowania

SOTE SORT to podział i podbij algorytm sortowania. W tym algorytmie nieporządkowana lista jest podzielona na dwie połowy za pomocą podziału liczb całkowitych. Każda z połówek jest ponownie podzielona na dwie połowy za pomocą podziału liczb całkowitych. Wydział ten trwa, dopóki lista zostanie uznana za pojedyncze oddzielne elementy.

Począwszy od lewej, kolejne elementy są następnie sparowane w sposób sortowany. Sparowane elementy są następnie ponownie sparowane w sortowanej formie. Ta grupa według par trwa do momentu zreformowania i sortowania całej listy.

Liniowa i logarytmiczna złożoność czasu

Rozważ następujący kod w języku C:

dla (int i = 0; i<8; i++)
int k = i + 1;
printf („%d”, k);

printf („\ n”);

Wyjście to:

1 2 3 4 5 6 7 8

Kod to pętla (ignorowanie instrukcji drukowania tuż po pętli). Wydrukuje liczby całkowite od 1 do 8, w sumie 8 liczb. Zawartość ciała na pętlę to:

int k = i + 1;
printf („%d”, k);

Te dwa stwierdzenia są uważane za jedną główną operację w tej sytuacji. Istnieje 8 operacji. Niech n będzie 8. Jest to liniowa złożoność czasu i jest ona napisana w następujący sposób:

NA)

Gdzie n jest możliwą maksymalną liczbą operacji. To jest notacja Big-O. Zaczyna się od O Uppercase, a następnie nawiasów. Wewnątrz nawiasów znajduje się maksymalna możliwa liczba operacji.

Zastanów się teraz nad następującym kodem, w którym z 8 liczb wydrukowane są 3 liczby:

dla (int i = 0; i<8; i++)
int k = i + 1;
printf („%d”, k);
if (k == 3) przerwa;

printf („\ n”);

Wyjście to:

1 2 3

Kod to pętla (ignorowanie instrukcji drukowania tuż po pętli). Wydrukuje liczby całkowite od 1 do 3 na 8 liczb. Zawartość ciała na pętlę to:

int k = i + 1;
printf („%d”, k);
if (k == 3) przerwa;

Mimo to te trzy stwierdzenia są uważane za jedną główną operację w tej sytuacji. Istnieją 3 operacje z 8.

Teraz,

8 = 2³
=> 3 = log₂(8)

Tak więc liczba głównych operacji przeprowadzonych przez poprzedni kod wynosi 3 (na 8).

Niech n będzie 8. Jest to logarytmiczna złożoność czasu i jest ona napisana jako:

O (log₂N)

Gdzie (log₂ n) oznacza 3 dla poprzedniego kodu.

Było 8 liczb. Zasadniczo, gdy liczba operacji kodu wynosi od 2 do 5 na 8, a nie tylko 3, złożoność czasu jest opisana jako dziennik₂(N).

Przykład listy nieporządonej i posortowanej

Przykładem listy nieprojektowanej jest następujący:

P V D Q S X T B

Na liście jest osiem elementów. Po sortowaniu tej listy staje się:

B D P Q S T V X

Liczenie liczby głównych operacji w sumie scalania

Poniższa lista:

P V D Q S X T B

służy do zliczenia liczby głównych operacji w sortowaniu scalania.

Dział liczb całkowitych przez dwa daje następujący wynik:

P V D Q S X T B

To jest jedna operacja. Kolejny podział obu części przez dwie daje następujący wynik:

P V D Q S X T B

Do tej pory są trzy operacje (jeden plus dwa). Kolejny podział każdej nowej części o dwóch daje następujący wynik:

P V D Q S X T B

Do tej pory są siedem operacji (trzy plus cztery). Lista ośmiu elementów jest obecnie uważana za osiem osobnych elementów z siedmioma dotychczasowymi operacjami. Następną fazą jest parowanie podczas sortowania, zaczynając od lewej. Kolejny wynik to:

P V D Q S X B T

Istnieją dwie zmiany pozycji dla ostatniej pary. Dwie zmiany to dwie operacje. To robi w sumie dziewięć operacji (siedem plus dwa).

Para i sortowanie trwa, zawsze zaczynając od lewej, aby dać następujący wynik:

D P Q V B S T x

Każda z tych dwóch grup miała cztery zmiany w pozycji, tworząc osiem operacji. Do tej pory istnieje siedemnaście operacji (dziewięć plus osiem). Para i sortowanie trwa i wreszcie, aby dać następujący wynik:

B D P Q S T V X

Jest tu siedem zmian w pozycji, tworząc siedem operacji. To sprawia, że ​​dwadzieścia cztery operacje (Seventeen Plus Seven) dla pełnego sortowania.

Złożoność czasu dla sortowania

Poprzednie liczenie (ilustracja) służy do zacytowania złożoności czasu dla scalania. Istnieje dwadzieścia cztery operacje.

24 = 8 x 3

To jest:

24 = 8 x dziennik₂(8)

Ponieważ log2 (8) to 3.

Niech 8 będzie n. Dzięki temu złożoność czasu scalania jest podana przez:

NA.dziennik₂N)

gdzie kropka oznacza mnożenie.

W praktyce spośród 8 elementów liczba operacji wynosi około 24 lub 24.

Wniosek

Scalesort jest szczególnym algorytmem sortowania i podbijania. Jest to bardzo wydajny algorytm sortowania. Jego złożoność czasu jest bardzo zadowalająca, w porównaniu z innymi algorytmami sortowania. Jego złożoność czasu to:

O (NLOG₂N)

Uwaga: liczba operacji niekoniecznie musi być dokładnie n.log2n . Powinien go jednak przybliżać.

Kodowanie scalania potrzebne funkcje rekurencyjne. Kodowanie go nie jest zbyt trudne po zrozumieniu algorytmu. Kodowanie sumienia jest dyskusją na jakiś czas.