Szybka złożoność czasu
Teraz istnieją różne sposoby pisania funkcji Pivot () i parition (). Wybór rodzaju funkcji Pivot () i/lub partycji () określa wydajność całego programu. Wydajność jest jak liczba głównych operacji przeprowadzanych przez program.
Złożoność czasu to względny czas wykonywania programu. Można to postrzegać jako główną operację programu.
Sortowanie może być rosnące lub zstępujące. W tym artykule sortowanie jest rosnące.
Celem tego artykułu jest stworzenie złożoności czasowej dla programu Quicksort. Ponieważ Quicksort może być pisany na różne sposoby w zależności od wyboru funkcji PIVOT () i/lub partycji (), każdy typ szybkiego sortowania ma własną złożoność czasu. Istnieje jednak szereg operacji, do których pasują różne typy programów Quicksort. W tym artykule przedstawiono tylko jeden z różnych rodzajów programów Quicksort. Każdy przedstawiony segment kodu jest z języka C.
Podział liczb całkowitych przez dwa
Szybki sort używa podziału liczb całkowitych w dzieleniu głównego zestawu na mniejsze zestawy.
Teraz,
11/2 = 5 pozostałym 1
Dywizja liczb całkowita oznacza, biorąc 5 lat i porzucając 1. To znaczy zaakceptuj liczbę całkowitą i zignoruj resztę.
Również,
10 /2 = 5 reszty 0
Tutaj reszta jest zerowa i nie ma znaczenia. Mimo to Division Integer bierze 5 i porzuca 0. To znaczy zaakceptuj liczbę całkowitą i zignoruj cokolwiek, co tam jest, nawet jeśli jest zero. Czasami w programowaniu dobrze jest również wiedzieć, czy reszta to 0, czy nie - patrz później.
Podczas dzielenia list.
Aby uzyskać szybki sort, aby uzyskać środkowy indeks oparty na zero dla listy, wykonaj podział całkowitego przez dwa na długości listy. Liczba całkowitą to zerowy, środkowy indeks. Aby uzyskać długość listy, zacznij liczyć od 1.
Złożoność czasu związana z szybkim sortowaniem
Rozważ następujący kod:
int n = 8;char a [] = „a”, „b”, „c”, „d”, „e”, „f”, „g”, „h”;
dla (int i = 0; i
printf („\ n”);
Wyjście to:
a b c d e f g hTo znaczy wszystkie osiem elementów zostało wydrukowanych.
Istnieje osiem elementów zidentyfikowanych przez n. Ciało na pętlę ma zawartość.
printf („%c”, a [i]);To jest jedna główna operacja. Tak więc miało miejsce osiem głównych operacji. Złożoność czasu dla tego kodu jest napisana jako:
NA)
Gdzie n jest liczbą głównych operacji. To jest notacja Big-O. W notacji pierwsza litera jest o O Gardzie. Potem są nawiasy. Wewnątrz nawiasów znajduje się liczba operacji lub maksymalna możliwa liczba operacji.
Teraz rozważ następujący segment kodu:
dla (int i = 0; i<8; i++)dla (int i = 0; i
if (i == 2)
przerwa;
printf („\ n”);
Wyjście to:
A B cCiało na pętlę ma zawartość.
printf („%c”, a [i]);if (i == 2)
przerwa;
Jest to nadal uważane za jedną główną operację w tej sytuacji. Wydrukowano trzy elementy, ponieważ główna operacja została wykonana trzy razy.
Teraz,
8 = 23
=> 3 = log2(8)
Jeśli 8 to n, to 3 to,
dziennik2(N)
A złożoność czasu byłaby podana jako:
O (log2N)
Do rozważenia jest jeszcze inny segment kodu w odniesieniu do złożoności czasowej Quicksort. To jest
dla (int i = 0; iprintf („\ n”);
printf („\ n”);
Wyjście to:
a b c d e f g ha b c d e f g h
a b c d e f g h
a b c d e f g h
a b c d e f g h
a b c d e f g h
a b c d e f g h
a b c d e f g h
Liczba wydrukowanych znaków wynosi 64, z początkowej liczby 8. Oznacza to, że główna operacja została wykonana 64 razy.
64 = 8 x 8 = 82
Jeśli 8 to n, to byłoby to n2. Złożoność czasu dla tego kodu jest:
NA2)
Algorytm szybkiego sortowania w tym artykule
W tym artykule kroki algorytmu to:
- Poszukaj mediany (patrz poniżej) między pierwszym elementem, środkowym elementem i ostatnim elementem listy.
- Ustaw medianę na środku listy.
- Wyślij wszystkie elementy po prawej, które są mniejsze niż mediana, teraz pośrodku, po lewej stronie mediany, i wyślij wszystkie elementy po lewej stronie, które są większe niż mediana po prawej stronie mediany. Nazywa się to partycjonowaniem.
- Powtórz powyższe trzy kroki w kolejności, dla każdej sub-listy, aż lista zostanie podzielona na pojedyncze elementy.
- Gdy lista składa się z oddzielonych pojedynczych elementów, lista jest sortowana.
Mediana
Aby uzyskać medianę trzech elementów,
TAKSÓWKAZmień kolejność trzech elementów, i.mi.
A B cŚrodkowy element B jest mediana.
Szybkie ilustracja
Lista do sortowania to:
P V D Q S X T BIstnieje osiem elementów. Kiedy lista została sortowana, byłoby to:
B D P Q S T V XProblem polega na: sortuj listę:
P V D Q S X T BKorzystanie z Quicksort.
Szukana jest mediana między P, Q i B. To jest p. To poszukiwanie mediany obejmuje trzy operacje. Tak więc do tej pory są trzy operacje. Umieszczenie mediany na środku listy daje:
V d q p s x t bPamiętaj: indeks środkowego elementu jest wynikiem podziału liczb całkowitych przez dwa. Są tu cztery ruchy, dla P i Q. To są cztery operacje. Dotyczy to w sumie siedmiu operacji (trzy plus cztery). Teraz B zostanie wysłany w lewo, a V i Q zostaną wysłane w prawo, aby mieć:
D B P V Q S X TZauważ, że P nie jest już w prawdziwym środku. Były jednak trzy ruchy. To są trzy operacje. Do tej pory jest dziesięć operacji (siedem plus trzy). Każda z dwóch podpisów musi zostać podzielona na trzy części (mediana to jedna część).
Mediana dla D i B wynosi D. Poszukiwanie mediany to trzy operacje. To wykonuje w sumie trzynaście operacji (dziesięć plus trzy). Podział tych elementów daje:
B dByły tutaj dwa ruchy. To są dwie operacje. To robi w sumie piętnaście operacji (trzynaście plus dwa). Następnie należy szukać mediany dla zestawu v, q, s, x, t.
Mediana dla V, S i T jest t. Mediana wyszukiwania to trzy operacje. Do tej pory odbyło się osiemnaście operacji (piętnaście plus trzy). Umieszczenie t na środku daje:
V q t s xSą tutaj trzy ruchy. To są trzy operacje. Całkowita liczba dotychczasowych operacji wynosi dwadzieścia jeden (osiemnaście plus trzy). Wysyłanie dolnych elementów po prawej stronie t po lewej i wyższe elementy po lewej stronie t po prawej, daje:
Q S T V XSą tutaj dwa ruchy. To są dwie operacje. Do tej pory istnieje w sumie dwadzieścia trzy operacje (dwadzieścia jeden plus dwa). Do tej pory łączenie wszystkich partycji daje:
B D P Q S T V XZauważ, że lista jest już posortowana. Jednak algorytm musi zakończyć. Q, s i v, x trzeba uczęszczać. Nie będzie ruchu postaci między tymi dwoma. Jednak ich mediana będzie patrzona. Poszukiwanie dwóch median to sześć operacji. To robi w sumie dwadzieścia dziewięć operacji dla całego programu (dwadzieścia trzy plus sześć). Ostateczna lista posortowana to:
B D P Q S T V XNotatka:
24 = 8 x 3
=> 24 = 8xlog28
29 jest w przybliżeniu równe 24.
Wniosek
W zależności od rodzaju funkcji wybranej dla Pivot () i rodzaju funkcji wybranej dla partycji (), złożoność czasu dla programu Quicksort będzie gdzieś pomiędzy
NA.dziennik2N)
I
NA2)
włącznie. Zauważ, że kropka w O (n.dziennik2n) oznacza mnożenie.