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.
- Kies altijd het eerste element als pivot.
- Kies altijd het laatste element als pivot (geïmplementeerd hieronder)
- Kies een willekeurig element als draaipunt.
- 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>