Wat is de tijdcomplexiteit van snel sorteren?

Beste antwoord

Omdat je genoeg kennis hebt van hoe Snel sorteren werkt, zoals het vinden van een draaipunt, het splitsen van de huidige array en opnieuw doen hetzelfde recursief voor elke subarrays, is het gemakkelijk om de tijdcomplexiteit te analyseren met de volgende zaken in overweging:

Worst Case:

Worst case doet zich voor wanneer we bij elke recursie het volgende draaipunt krijgen om arrays te splitsen aan het einde van de array.

Als N is de lengte van de array en met de huidige pivot op de startpositie van de array,

pivot at last index wordt alleen geïdentificeerd als de array van begin tot eind doorloopt. Na het vastzetten van het draaipunt en het splitsen zijn de resulterende subarrays met een lengte (N-1), 1 .

Nogmaals, dit (N-1) subarray vindt het volgende draaipunt bij de laatste index resulterende arraypartities met lengtes (N-2), 1 .

Dit proces herhaalt zich totdat de uiteindelijke lengte van de subarrays beide 1,1 is.

Dus dit kan wiskundig in papier worden getekend als

bij stap 1: met N elementen is de tijdcomplexiteit voor deze partitie

T (N) = N + T (N-1)

Waarbij T (N-1) de tijdcomplexiteit is van de partitie naar worden recursief verwerkt en N is de tijd die nodig is om N-elementen met een vast draaipunt te vergelijken.

bij stap 2: met N-1 -elementen ,

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 omdat de tijd voor het partitioneren van array met lengte 1 0 is zonder partities

Vandaar

T (N) = N + (N-1) + (N-2) … + 3 + 2 ≈ N * (N + 1) / 2

= (N ^ 2) / 2

= O (N ^ 2)

Gemiddeld aantal gevallen :

In gemiddeld geval splitst de volgende pivot de array in twee gelijke lengtes (N / 2) door te vergelijken alle elementen die resulteren in tijdcomplexiteit N.

T (N) = 2 * T (N / 2) + N

beide zijden delen door N

T (N) / N = 2 * (T (N / 2) / N) + N / N

T (N) / N = 2 * (T (N / 2) / N) + 1

Daarom, 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

Zoals 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) termen

Daarom T (N) / N = log N

T (N) = NlogN

Answer

QuickSort is een verdeel en heers-algoritme. Het kiest een element als draaipunt en verdeelt de gegeven array rond het gekozen draaipunt. Er zijn veel verschillende versies van quickSort die pivot op verschillende manieren aanwijzen.

  1. Kies altijd het eerste element als pivot.
  2. Kies altijd het laatste element als pivot (geïmplementeerd hieronder)
  3. Kies een willekeurig element als draaipunt.
  4. Kies de mediaan als draaipunt.

Het belangrijkste proces in quickSort is een partitie ( ). Het doel van partities is, gegeven een array en een element x van de array als draaipunt, x op de juiste positie in een gesorteerde array plaatsen en alle kleinere elementen (kleiner dan x) voor x plaatsen, en alle grotere elementen (groter dan x) na x. Dit alles moet in lineaire tijd gebeuren.

Stappen van quicksort zijn:

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

Implementatie van 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)

}

}

Tijdscomplexiteit van quicksort:

Slechtste Geval: Het ergste geval doet zich voor wanneer het partitieproces altijd het grootste of kleinste element als spil kiest. Als we de bovenstaande partitiestrategie beschouwen waarbij het laatste element altijd als draaipunt wordt gekozen, zou het ergste geval zich voordoen wanneer de array al in oplopende of aflopende volgorde is gesorteerd. Hieronder volgt een herhaling voor het ergste geval.

T(n) = T(0) + T(n-1) + (n)

which is equivalent to

T(n) = T(n-1) + (n)

De complexiteit van de bovenstaande herhaling is n vierkant

Beste geval: Het beste geval doet zich voor wanneer het partitieproces altijd kiest het middelste element als spil. Hieronder volgt een herhaling voor het beste geval.

T(n) = 2T(n/2) + (n)

De complexiteit van de bovenstaande herhaling is nLogn

Gemiddeld geval: Om een ​​gemiddelde case-analyse uit te voeren, moeten we alle mogelijke permutaties van de array in overweging nemen en de tijd berekenen die elke permutatie kost, wat er niet gemakkelijk uitziet. We kunnen een idee krijgen van het gemiddelde geval door te kijken naar het geval waarin partitie O (n / 9) -elementen in één set plaatst en O (9n / 10) -elementen in andere sets. Hieronder volgt een herhaling voor dit geval.

T(n) = T(n/9) + T(9n/10) + (n)

De complexiteit van de bovenstaande herhaling is nLogn

Ruimtecomplexiteit van quicksort :

De ruimte die door quicksort wordt gebruikt, is afhankelijk van de gebruikte versie.

De in-place versie van quicksort heeft een ruimtecomplexiteit van O (log n), zelfs in in het ergste geval, wanneer het zorgvuldig wordt geïmplementeerd met behulp van de volgende strategieën:

  • in-place partitionering wordt gebruikt. Deze onstabiele partitie heeft O (1) ruimte nodig.
  • Na het partitioneren wordt de partitie met de minste elementen eerst (recursief) gesorteerd, waarbij maximaal O (log n) ruimte nodig is. Vervolgens wordt de andere partitie gesorteerd met behulp van staartrecursie of iteratie, wat niet bijdraagt ​​aan de call-stack. Dit idee, zoals hierboven besproken, werd beschreven door R. Sedgewick, en houdt de stack-diepte begrensd door O (log n). / li>

Geef een reactie

Het e-mailadres wordt niet gepubliceerd. Vereiste velden zijn gemarkeerd met *