Beste svaret
Da du har nok kunnskap om hvordan Quick Sort fungerer, som å finne pivot, dele den nåværende matrisen og igjen gjøre det samme rekursivt for hver underarray, er det enkelt å analysere tidskompleksitet med disse tingene i betraktning:
Verste tilfelle:
Verste tilfelle oppstår når vi ved hver rekursjon får neste sving for å dele opp matriser er på slutten av matrisen.
Hvis N er lengden på matrisen og har nåværende pivot ved startposisjonen til arrayet,
pivot at last index er bare identifisert som traversing array fra start til slutt. Etter å ha løst pivot og splitting er resulterende underarrayer av lengde (N-1), 1 .
Igjen dette (N-1) underarray finner neste pivot ved siste indeks resulterende arraypartisjoner med lengder (N-2), 1 .
Denne prosessen gjentas til de endelige underarraylengdene er begge 1,1 .
Så dette kan matematisk tegnes inn i papir som
i trinn 1: med N elementer, er tidskompleksiteten for denne partisjonen
T (N) = N + T (N-1)
Hvor T (N-1) er tidskompleksitet av partisjon til behandles rekursivt, og N er tiden det tar å sammenligne N-elementer med en fast pivot.
i trinn 2: med N-1 -elementer ,
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 til partisjonssamling med lengden 1 er 0 uten partisjoner
Derfor,
T (N) = N + (N-1) + (N-2) … + 3 + 2 ≈ N * (N + 1) / 2
= (N ^ 2) / 2
= O (N ^ 2)
Gjennomsnittlig sak :
I gjennomsnitt tilfeller deler neste pivot delingen i to like lengder (N / 2) ved å sammenligne alle elementer som resulterer i tidskompleksitet N.
T (N) = 2 * T (N / 2) + N
del begge sider med N
T (N) / N = 2 * (T (N / 2) / N) + N / N
T (N) / N = 2 * (T (N / 2) / N) + 1
Derfor er 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
Derfor T (N) / N = log N
T (N) = NlogN
Svar
QuickSort er en Divide and Conquer-algoritme. Den plukker et element som pivot og partisjonerer den gitte matrisen rundt den valgte pivoten. Det er mange forskjellige versjoner av quickSort som velger pivot på forskjellige måter.
- Velg alltid det første elementet som en pivot.
- Velg alltid det siste elementet som pivot (implementert nedenfor)
- Velg et tilfeldig element som pivot.
- Velg medianen som en pivot.
Nøkkelprosessen i quickSort er en partisjon ( ). Målet for partisjoner er, gitt en matrise og et element x i matrisen som en pivot, setter x i riktig posisjon i en sortert matrise og setter alle mindre elementer (mindre enn x) foran x, og setter alle større elementer (større enn x) etter x. Alt dette bør gjøres på lineær tid.
Trinn for kviksort er:
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 quickort:
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)
}
}
Tidskompleksitet for kviksort:
Verst Sak: Det verste tilfellet oppstår når partisjonsprosessen alltid velger det største eller minste elementet som pivot. Hvis vi vurderer den ovennevnte partisjonsstrategien der det siste elementet alltid blir valgt som en pivot, vil det verste tilfellet oppstå når matrisen allerede er sortert i økende eller synkende rekkefølge. Følgende er gjentakelse i verste fall.
T(n) = T(0) + T(n-1) + (n)
which is equivalent to
T(n) = T(n-1) + (n)
Kompleksiteten til ovennevnte gjentakelse er n kvadrat
Best case: Best case oppstår når partisjonsprosessen alltid velger midtelementet som dreiepunkt. Følgende er en gjentakelse for det beste.
T(n) = 2T(n/2) + (n)
Kompleksiteten til gjentakelsen ovenfor er nLogn
Gjennomsnittlig sak: For å gjøre gjennomsnittlig saksanalyse må vi vurdere all mulig permutasjon av matrisen og beregne tiden det tar av hver permutasjon som ikke ser lett ut. Vi kan få en ide om gjennomsnittssaken ved å vurdere saken når partisjonen setter O (n / 9) -elementer i ett sett og O (9n / 10) -elementer i andre sett. Følgende er en gjentakelse for denne saken.
T(n) = T(n/9) + T(9n/10) + (n)
Kompleksiteten til gjentakelsen ovenfor er nLogn
Rikskompleksitet i kviksort :
Plassen som brukes av quicksort, avhenger av hvilken versjon som brukes.
Den stedlige versjonen av quicksort har en mellomromskompleksitet på O (log n), selv i i verste fall når den er nøye implementert ved hjelp av følgende strategier:
- stedlig partisjonering brukes. Denne ustabile partisjonen krever O (1) plass.
- Etter partisjonering sorteres partisjonen med færrest elementer (rekursivt) først, og krever maksimalt O (log n) plass. Deretter sorteres den andre partisjonen ved hjelp av hale-rekursjon eller iterasjon, som ikke legger til samtalestakken. Denne ideen, som diskutert ovenfor, ble beskrevet av R. Sedgewick, og holder stabeldybden avgrenset av O (log n).