Cel mai bun răspuns
Deoarece aveți suficiente cunoștințe despre modul în care funcționează Sortarea rapidă, cum ar fi găsirea pivotului, împărțirea matricei curente și din nou la fel recursiv pentru fiecare sub-matrice, este ușor să analizăm complexitatea timpului cu aceste lucruri luate în considerare:
Cel mai rău caz apare atunci când la fiecare recursiune obținem următorul pivot pentru a împărți matricele este la sfârșitul matricei.
Dacă N este lungimea tabloului și având pivotul curent la poziția de pornire a tabloului,
pivotul la ultimul index este identificat doar traversând matricea de la început până la sfârșit. După fixarea pivotului și împărțirea sub-tablourilor rezultate de lungime sunt (N-1), 1 .
Din nou acest „> (N-1) sub matrice găsește următorul pivot la ultimul index partiții matrice rezultate cu lungimi (N-2), 1 .
Acest proces se repetă până când lungimile sub-matrice finale sunt ambele 1,1 .
Deci, acest lucru poate fi desenat matematic în hârtie ca
la pasul 1: cu N elemente, complexitatea timpului pentru această partiție este
T (N) = N + T (N-1)
Unde T (N-1) este complexitatea în timp a partiției către să fie procesat recursiv și N este timpul necesar pentru a compara N elemente cu un pivot fix.
la pasul 2: cu N-1 ,
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, deoarece timpul pentru partiționarea matricei cu lungimea 1 este 0 fără partiții
Prin urmare,
T (N) = N + (N-1) + (N-2) … + 3 + 2 ≈ N * (N + 1) / 2
= (N ^ 2) / 2
= O (N ^ 2)
Caz mediu :
În cazul mediu, următorul pivot împarte matricea în două lungimi egale (N / 2) comparând toate elementele care au ca rezultat complexitatea timpului N.
T (N) = 2 * T (N / 2) + N
împarte ambele părți la N
T (N) / N = 2 * (T (N / 2) / N) + N / N
T (N) / N = 2 * (T (N / 2) / N) + 1
Prin urmare, 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
As 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) termeni
Prin urmare T (N) / N = log N
T (N) = NlogN
Răspuns
QuickSort este un algoritm Divide and Conquer. Acesta alege un element ca pivot și partiționează matricea dată în jurul pivotului ales. Există multe versiuni diferite de quickSort care aleg pivot în moduri diferite.
- Alegeți întotdeauna primul element ca pivot.
- Alegeți întotdeauna ultimul element ca pivot (implementat mai jos)
- Alegeți un element aleatoriu ca pivot.
- Alegeți mediana ca pivot.
Procesul cheie în quickSort este o partiție ( ). Ținta partițiilor este, având în vedere un tablou și un element x al tabloului ca pivot, pune x la poziția corectă într-un tablou sortat și pune toate elementele mai mici (mai mici decât x) înainte de x și pune toate elementele mai mari (mai mare decât x) după x. Toate acestea trebuie făcute în timp liniar.
Pașii rapide sunt:
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
Implementarea 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)
}
}
Complexitatea temporală a quicksort:
Cel mai rău Caz: Cel mai rău caz apare atunci când procesul de partiție alege întotdeauna cel mai mare sau cel mai mic element ca pivot. Dacă luăm în considerare strategia de partiție de mai sus în care ultimul element este întotdeauna ales ca un pivot, cel mai rău caz ar apărea atunci când matricea este deja sortată în ordine crescătoare sau descrescătoare. Urmează recurența pentru cel mai rău caz.
T(n) = T(0) + T(n-1) + (n)
which is equivalent to
T(n) = T(n-1) + (n)
Complexitatea recurenței de mai sus este n pătrat
Cel mai bun caz: Cel mai bun caz apare atunci când procesul de partiție alege întotdeauna elementul de mijloc ca pivot. Urmează o recurență pentru cel mai bun caz.
T(n) = 2T(n/2) + (n)
Complexitatea recurenței de mai sus este nLogn
Caz mediu: Pentru a face o analiză medie de caz, trebuie să luăm în considerare toate permutările posibile ale matricei și să calculăm timpul necesar fiecărei permutări care nu pare ușor. Putem face o idee despre cazul mediu luând în considerare cazul când partiția pune elementele O (n / 9) într-un set și elementele O (9n / 10) în alte seturi. Urmează o recurență pentru acest caz.
T(n) = T(n/9) + T(9n/10) + (n)
Complexitatea recurenței de mai sus este nLogn
Complexitatea spațială a quicksort :
Spațiul folosit de quicksort depinde de versiunea utilizată.
Versiunea în loc de quicksort are o complexitate spațială de O (log n), chiar și în cel mai rău caz, atunci când este implementat cu atenție folosind următoarele strategii:
- este utilizată partiționarea în loc. Această partiție instabilă necesită spațiu O (1).
- După partiționare, partiția cu cele mai puține elemente este (recursiv) sortată mai întâi, necesitând cel mult spațiu O (log n). Apoi cealaltă partiție este sortată folosind recursivitate sau iterație de coadă, care nu se adaugă la stiva de apeluri. Această idee, așa cum s-a discutat mai sus, a fost descrisă de R. Sedgewick și păstrează adâncimea stivei mărginită de O (log n).