Bästa svaret
Eftersom du har tillräckligt med kunskap om hur Quick Sort fungerar, som att hitta pivot, dela upp nuvarande array och göra igen samma rekursivt för varje undergrupp, det är lätt att analysera tidskomplexitet med dessa saker i beaktande:
Värsta fall:
Värsta fall inträffar när vi vid varje rekursion får nästa pivot för att dela arrays är i slutet av arrayen.
Om N är längden på matrisen och har aktuell pivot vid matrisens startposition,
pivot at last index identifieras endast genomgående array från start till slut. Efter fixering av pivot och delning är resulterande undermatriser med längd (N-1), 1 .
Återigen detta (N-1) underarray hittar nästa pivot vid sista index resulterande arraypartitioner med längder (N-2), 1 .
Denna process upprepas tills de slutliga underarraylängderna båda är 1,1 .
Så detta kan matematiskt ritas till papper som
i steg 1: med N -element är tidskomplexiteten för denna partition
T (N) = N + T (N-1)
Där T (N-1) är tidskomplexitet för partition till behandlas rekursivt och N är den tid som krävs för att jämföra N-element med en fast pivot.
i steg 2: med N-1 -element ,
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 som tid till partitionsarray med längd 1 är 0 utan partitioner
Därför
T (N) = N + (N-1) + (N-2) … + 3 + 2 ≈ N * (N + 1) / 2
= (N ^ 2) / 2
= O (N ^ 2)
Genomsnittligt fall :
I genomsnitt fallar nästa pivot upp matrisen i två lika långa (N / 2) genom att jämföra alla element som resulterar i tidskomplexitet N.
T (N) = 2 * T (N / 2) + N
dela båda sidor med N
T (N) / N = 2 * (T (N / 2) / N) + N / N
T (N) / N = 2 * (T (N / 2) / N) + 1
Därför är 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
Som 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) termer
Därför T (N) / N = log N
T (N) = NlogN
Svar
QuickSort är en Divide and Conquer-algoritm. Det väljer ett element som pivot och partitionerar den givna matrisen runt den valda pivoten. Det finns många olika versioner av quickSort som väljer pivot på olika sätt.
- Välj alltid det första elementet som en pivot.
- Välj alltid det sista elementet som pivot (implementerat nedan)
- Välj ett slumpmässigt element som pivot.
- Välj medianen som en pivot.
Nyckelprocessen i quickSort är en partition ( ). Målet för partitioner är att, ges en matris och ett element x i matrisen som en pivot, placerar x i rätt position i en sorterad matris och placerar alla mindre element (mindre än x) före x, och placerar alla större element (större än x) efter x. Allt detta bör göras linjärt.
Steg för quicksort är:
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
Implementering av snabbsort:
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)
}
}
Snabbsortens tidskomplexitet:
Värst Fall: Det värsta fallet inträffar när partitionsprocessen alltid väljer det största eller minsta elementet som led. Om vi tar hänsyn till ovanstående partitionsstrategi där det sista elementet alltid väljs som en pivot, skulle det värsta fallet inträffa när arrayen redan är sorterad i ökande eller minskande ordning. Följande är återfall i värsta fall.
T(n) = T(0) + T(n-1) + (n)
which is equivalent to
T(n) = T(n-1) + (n)
Komplexiteten hos ovanstående upprepning är n kvadrat
Bästa fall: Det bästa fallet inträffar när partitionsprocessen alltid väljer mittelementet som pivot. Följande är en upprepning i bästa fall.
T(n) = 2T(n/2) + (n)
Komplexiteten hos ovanstående upprepning är nLogn
Genomsnittligt fall: För att göra en genomsnittlig fallanalys måste vi överväga all möjlig permutation av arrayen och beräkna den tid det tar för varje permutation som inte ser lätt ut. Vi kan få en uppfattning om medelfallet genom att överväga fallet när partitionen sätter O (n / 9) -element i en uppsättning och O (9n / 10) -element i andra uppsättningar. Följande är en upprepning för detta fall.
T(n) = T(n/9) + T(9n/10) + (n)
Komplexiteten hos ovanstående upprepning är nLogn
Quicksorts rymdkomplexitet :
Utrymmet som används av quicksort beror på vilken version som används.
Den platsversionen av quicksort har en mellanslagskomplexitet O (log n), även i i värsta fall, när den omsorgsfullt implementeras med följande strategier:
- partitionering används på plats. Denna instabila partition kräver O (1) utrymme.
- Efter partition sorteras partitionen med minst element (rekursivt) först och kräver högst O (log n) utrymme. Sedan sorteras den andra partitionen med hjälp av svansrekursion eller iteration, vilket inte lägger till samtalsstacken. Denna idé, som diskuterats ovan, beskrevs av R. Sedgewick och håller stackdjupet begränsat av O (log n).