Najlepsza odpowiedź
Ponieważ masz wystarczającą wiedzę na temat działania szybkiego sortowania, na przykład znajdowania przestawienia, dzielenia bieżącej tablicy i ponownego wykonywania tak samo rekurencyjnie dla każdej tablicy podrzędnej, łatwo jest przeanalizować złożoność czasową, biorąc pod uwagę następujące kwestie:
Najgorszy przypadek:
Najgorszy przypadek ma miejsce, gdy przy każdej rekurencji otrzymujemy następny przestawienie dzielenia tablic na koniec tablicy.
Jeśli N jest długością tablicy i ma bieżący punkt obrotu w pozycji początkowej tablicy,
punkt obrotu w ostatnim indeksie jest identyfikowany tylko podczas przechodzenia przez tablicę od początku do końca. Po ustaleniu obrotu i podzieleniu wynikowych tablic podrzędnych o długości to (N-1), 1 .
Ponownie to (N-1) tablica podrzędna znajduje następną tabelę przestawną w ostatnim indeksie, wynikowe partycje tablicy o długościach (N-2), 1 .
Ten proces powtarza się, dopóki długość końcowych pod tablic nie osiągnie wartości 1,1 .
Więc to można matematycznie narysować na papierze jako
w kroku 1: z elementami N , złożoność czasowa dla tej partycji wynosi
T (N) = N + T (N-1)
Gdzie T (N-1) to czasowa złożoność podziału na być przetwarzane rekurencyjnie, a N to czas potrzebny do porównania N elementów ze stałym obrotem.
w kroku 2: z N-1 elementami ,
T (N-1) = (N-1) + T (N-2)
T (N-2) = (N-2) + T (N-3)
…
T (3) = 3 + T (2)
T (2) = 2 + T (1)
T ( 1) = 0 jako czas podziału tablicy o długości 1 wynosi 0 bez partycji
Stąd
T (N) = N + (N-1) + (N-2) … + 3 + 2 ≈ N * (N + 1) / 2
= (N ^ 2) / 2
= O (N ^ 2)
Średnia wielkość :
W średnim przypadku następny element przestawny dzieli tablicę na dwie równe długości (N / 2) , porównując wszystkie elementy, które powodują złożoność czasową N.
T (N) = 2 * T (N / 2) + N
podziel obie strony przez N
T (N) / N = 2 * (T (N / 2) / N) + N / N
T (N) / N = 2 * (T (N / 2) / N) + 1
Dlatego T (N) / N = (T (N / 2) / (N / 2)) + 1
T (N / 2) / (N / 2) = T (N / 4) / (N / 4) + 1
…
T (2) / 2 = T (1) / 1 + 1
Jak T (1) = 0
T (2) / 2 = 1
T (4) / 4 = T (2) + T (1)
T (8) / 8 = T (4) + T (2) + T (1) ## log (n) wyrazy
Zatem T (N) / N = log N
T (N) = NlogN
Odpowiedź
QuickSort to algorytm dziel i zwyciężaj. Wybiera element jako pivot i dzieli daną tablicę wokół wybranego pivota. Istnieje wiele różnych wersji quickSort, które wybierają przestawienie na różne sposoby.
- Zawsze wybieraj pierwszy element jako przestawny.
- Zawsze wybieraj ostatni element jako przestawny (zaimplementowane poniżej)
- Wybierz losowy element jako przestawny.
- Wybierz medianę jako zmienną.
Kluczowym procesem w quickSort jest partycja ( ). Celem partycji jest, mając tablicę i element x tablicy jako przestawienie, umieścić x na jego prawidłowej pozycji w posortowanej tablicy i umieścić wszystkie mniejsze elementy (mniejsze niż x) przed x i umieścić wszystkie większe elementy (większe niż x) po x. Wszystko to powinno odbywać się w czasie liniowym.
Kroki szybkiego sortowania to:
Step 1 − Choose the highest index value has a pivot
Step 2 − Take two variables to point left and right of the list excluding pivot
Step 3 − left points to the low index
Step 4 − right points to the high
Step 5 − while value at left is less than pivot move right
Step 6 − while value at the right is greater than pivot move left
Step 7 − if both step 5 and step 6 does not match swap left and right
Step 8 − if left ≥ right, the point where they met is the new pivot
Implementacja quicksort:
Quicksort(A,p,r) {
if (p
q
Quicksort(A,p,q)
Quicksort(A,q+1,r)
}
}
Partition(A,p,r)
x
i
j
while (True) {
repeat
j
until (A[j]
i
until (A[i] >= x)
if (i A[j]
else
return(j)
}
}
Złożoność czasowa szybkiego sortowania:
Najgorszy Przypadek: Najgorszy przypadek występuje, gdy proces partycjonowania zawsze wybiera największy lub najmniejszy element jako element przestawny. Jeśli weźmiemy pod uwagę powyższą strategię partycjonowania, w której ostatni element jest zawsze wybierany jako przestawny, najgorszy przypadek miałby miejsce, gdy tablica jest już posortowana w kolejności rosnącej lub malejącej. Poniżej znajduje się powtórzenie w najgorszym przypadku.
T(n) = T(0) + T(n-1) + (n)
which is equivalent to
T(n) = T(n-1) + (n)
Złożoność powyższej powtarzalności wynosi n kwadrat
Najlepszy przypadek: Najlepszy przypadek występuje, gdy proces partycjonowania zawsze wybiera środkowy element jako pivot. Poniżej znajduje się powtórzenie w najlepszym przypadku.
T(n) = 2T(n/2) + (n)
Złożoność powyższego powtórzenia wynosi nLogn
Średnia wielkość: Aby przeprowadzić analizę przeciętnego przypadku, musimy rozważyć wszystkie możliwe permutacje tablicy i obliczyć czas potrzebny na każdą permutację, co nie wygląda na łatwe. Możemy zrozumieć przypadek średni, rozważając przypadek, w którym partycja umieszcza O (n / 9) elementów w jednym zestawie i O (9n / 10) elementów w innych zbiorach. Poniżej znajduje się powtórzenie dla tego przypadku.
T(n) = T(n/9) + T(9n/10) + (n)
Złożoność powyższego powtórzenia wynosi nLogn
Przestrzenna złożoność szybkiego sortowania :
Miejsce zajmowane przez quicksort zależy od używanej wersji.
Lokalna wersja quicksort ma złożoność przestrzeni O (log n), nawet w w najgorszym przypadku, gdy jest starannie zaimplementowany przy użyciu następujących strategii:
- stosowane jest partycjonowanie w miejscu. Ta niestabilna partycja wymaga O (1) miejsca.
- Po partycjonowaniu partycja z najmniejszą liczbą elementów jest (rekurencyjnie) sortowana jako pierwsza, wymagając co najwyżej O (log n) miejsca. Następnie druga partycja jest sortowana za pomocą rekurencji ogonowej lub iteracji, która nie dodaje do stosu wywołań. Pomysł ten, jak omówiono powyżej, został opisany przez R. Sedgewicka i utrzymuje głębokość stosu ograniczoną przez O (log n).