Bedste svar
Da du har tilstrækkelig viden om, hvordan Quick Sort fungerer, som at finde pivot, opdele det aktuelle array og igen gøre det samme rekursivt for hver underarray, er det let at analysere tidskompleksitet med disse ting i betragtning:
Worst Case:
Worst case opstår, når vi ved hver rekursion får den næste drejning om at opdele arrays er i slutningen af arrayet.
Hvis N er længden af arrayet og har den aktuelle drejning ved startpositionen for arrayet,
pivot at last index identificeres kun gennemkørsel af array fra start til slut. Efter at have fastgjort drejning og opdeling er resulterende underarray af længde (N-1), 1 .
Igen dette (N-1) underarray finder næste pivot ved sidste indeks resulterende arraypartitioner med længder (N-2), 1 .
Denne proces gentages, indtil de endelige underarraylængder begge er 1,1 .
Så dette kan matematisk trækkes ind i papir som
i trin 1: med N -elementer er tidskompleksiteten for denne partition
T (N) = N + T (N-1)
Hvor T (N-1) er tidskompleksitet af partition til behandles rekursivt, og N er den nødvendige tid til at sammenligne N-elementer med en fast drejning.
i trin 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 partitionsarray med længden 1 er 0 uden partitioner
Derfor
T (N) = N + (N-1) + (N-2) … + 3 + 2 ≈ N * (N + 1) / 2
= (N ^ 2) / 2
= O (N ^ 2)
Gennemsnitlig sag :
I gennemsnit falder den næste pivot op i to lige store længder (N / 2) ved at sammenligne alle elementer, der resulterer i tidskompleksitet N.
T (N) = 2 * T (N / 2) + N
divider 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) udtryk
Derfor T (N) / N = log N
T (N) = NlogN
Svar
QuickSort er en Divide and Conquer algoritme. Det vælger et element som pivot og partitionerer det givne array omkring det valgte pivot. Der er mange forskellige versioner af quickSort, der vælger pivot på forskellige måder.
- Vælg altid det første element som en pivot.
- Vælg altid det sidste element som pivot (implementeret nedenfor)
- Vælg et tilfældigt element som pivot.
- Vælg medianen som en pivot.
Nøgleprocessen i quickSort er en partition ( ). Målet for partitioner er, givet en matrix og et element x i arrayet som en drejetap, sætter x på sin korrekte position i et sorteret array og sætter alle mindre elementer (mindre end x) foran x, og sætter alle større elementer (større end x) efter x. Alt dette skal ske i lineær tid.
Trin til quicksort 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 af 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)
}
}
Quicksort-tidskompleksitet:
Værst Tilfælde: Det værste tilfælde opstår, når delingsprocessen altid vælger det største eller mindste element som omdrejningspunkt. Hvis vi overvejer ovenstående partitionsstrategi, hvor det sidste element altid vælges som en drejetap, ville det værste tilfælde forekomme, når arrayet allerede er sorteret i stigende eller faldende rækkefølge. Følgende er i værste fald gentagelse.
T(n) = T(0) + T(n-1) + (n)
which is equivalent to
T(n) = T(n-1) + (n)
Kompleksiteten af ovenstående gentagelse er n kvadratisk
Bedste tilfælde: Bedste tilfælde opstår, når partitionsprocessen altid vælger det midterste element som drejning. Følgende er en gentagelse i bedste fald.
T(n) = 2T(n/2) + (n)
Kompleksiteten af ovenstående gentagelse er nLogn
Gennemsnitlig sag: For at udføre en gennemsnitlig sagsanalyse er vi nødt til at overveje al mulig permutation af arrayet og beregne den tid, det tager af hver permutation, der ikke ser let ud. Vi kan få en idé om gennemsnittet ved at overveje tilfældet, når partitionen placerer O (n / 9) -elementer i et sæt og O (9n / 10) -elementerne i andre sæt. Følgende er en gentagelse af denne sag.
T(n) = T(n/9) + T(9n/10) + (n)
Kompleksiteten af ovenstående gentagelse er nLogn
Quicksorts rumkompleksitet :
Den plads, der bruges af quicksort, afhænger af den anvendte version.
Den stedlige version af quicksort har en mellemrumskompleksitet på O (log n), selv i i værste fald, når det er omhyggeligt implementeret ved hjælp af følgende strategier:
- anvendes partitionering på stedet. Denne ustabile partition kræver O (1) plads.
- Efter partition sorteres partitionen med de færreste elementer (rekursivt) først og kræver højst O (log n) plads. Derefter sorteres den anden partition ved hjælp af hale rekursion eller iteration, som ikke føjer til opkaldstakken. Denne idé, som beskrevet ovenfor, blev beskrevet af R. Sedgewick og holder stakdybden afgrænset af O (log n).