Jaka jest złożoność czasowa szybkiego sortowania?

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.

  1. Zawsze wybieraj pierwszy element jako przestawny.
  2. Zawsze wybieraj ostatni element jako przestawny (zaimplementowane poniżej)
  3. Wybierz losowy element jako przestawny.
  4. 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).

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *