Risposta migliore
Dato che hai una conoscenza sufficiente di come funziona lordinamento rapido, come trovare pivot, dividere larray corrente e di nuovo lo stesso in modo ricorsivo per ogni sottoinsieme, è facile analizzare la complessità temporale tenendo conto di queste cose:
Caso peggiore:
Il caso peggiore si verifica quando ad ogni ricorsione otteniamo il pivot successivo per dividere gli array è alla fine dellarray.
Se N è la lunghezza dellarray e il pivot corrente nella posizione iniziale dellarray,
il pivot allultimo indice viene identificato solo attraversando larray dallinizio alla fine. Dopo aver corretto il pivot e aver suddiviso i sotto array risultanti di lunghezza sono (N-1), 1 .
Di nuovo questo (N-1) larray secondario trova il pivot successivo allultimo indice partizioni dellarray risultanti con lunghezze (N-2), 1 .
Questo processo si ripete fino a quando le lunghezze degli array secondari finali sono entrambi 1,1 .
Quindi, questo può essere matematicamente disegnato su carta come
al passaggio 1: con N elementi, la complessità temporale per questa partizione è
T (N) = N + T (N-1)
Dove T (N-1) è la complessità temporale della partizione a essere elaborato in modo ricorsivo e N è il tempo necessario per confrontare N elementi con un pivot fisso.
al passaggio 2: con N-1 elementi ,
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 in quanto il tempo per partizionare un array con lunghezza “1” è 0 senza partizioni
Quindi,
T (N) = N + (N-1) + (N-2) … + 3 + 2 ≈ N * (N + 1) / 2
= (N ^ 2) / 2
= O (N ^ 2)
Caso medio :
In caso medio il pivot successivo divide larray in due lunghezze uguali (N / 2) confrontando tutti gli elementi che risultano in complessità temporale N.
T (N) = 2 * T (N / 2) + N
dividi entrambi i lati per N
T (N) / N = 2 * (T (N / 2) / N) + N / N
T (N) / N = 2 * (T (N / 2) / N) + 1
Pertanto, 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
Come 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) termini
Quindi T (N) / N = log N
T (N) = NlogN
Risposta
QuickSort è un algoritmo Divide and Conquer. Sceglie un elemento come pivot e partiziona larray dato attorno al pivot selezionato. Esistono molte versioni differenti di quickSort che selezionano il pivot in modi diversi.
- Scegli sempre il primo elemento come pivot.
- Scegli sempre lultimo elemento come pivot (implementato sotto)
- Scegli un elemento casuale come pivot.
- Scegli la mediana come pivot.
Il processo chiave in quickSort è una partizione ( ). Lobiettivo delle partizioni è, dato un array e un elemento x dellarray come pivot, mettere x nella sua posizione corretta in un array ordinato e mettere tutti gli elementi più piccoli (più piccoli di x) prima di x, e inserire tutti gli elementi maggiori (maggiore di x) dopo x. Tutto questo dovrebbe essere fatto in tempo lineare.
I passaggi di quicksort sono:
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
Implementazione di 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)
}
}
Complessità temporale di quicksort:
Peggiore Case: Il caso peggiore si verifica quando il processo di partizione sceglie sempre lelemento più grande o più piccolo come pivot. Se consideriamo la strategia di partizione di cui sopra in cui lultimo elemento viene sempre scelto come pivot, il caso peggiore si verificherebbe quando larray è già ordinato in ordine crescente o decrescente. Di seguito è indicata la ricorrenza nel caso peggiore.
T(n) = T(0) + T(n-1) + (n)
which is equivalent to
T(n) = T(n-1) + (n)
La complessità della ricorrenza precedente è n quadrato
Caso migliore: Il caso migliore si verifica quando il processo di partizione sceglie sempre lelemento centrale come perno. Di seguito è riportata una ricorrenza per il caso migliore.
T(n) = 2T(n/2) + (n)
La complessità della ricorrenza precedente è nLogn
Caso medio: Per fare unanalisi del caso medio, dobbiamo considerare tutte le possibili permutazioni dellarray e calcolare il tempo impiegato da ogni permutazione che non sembra facile. Possiamo avere unidea del caso medio considerando il caso in cui la partizione inserisce O (n / 9) elementi in un insieme e O (9n / 10) elementi in altri insiemi. Di seguito è riportata una ricorrenza per questo caso.
T(n) = T(n/9) + T(9n/10) + (n)
La complessità della ricorrenza sopra è nLogn
Complessità dello spazio di quicksort :
Lo spazio utilizzato da quicksort dipende dalla versione utilizzata.
La versione sul posto di quicksort ha una complessità di spazio di O (log n), anche in il caso peggiore, quando viene implementato con cura utilizzando le seguenti strategie:
- viene utilizzato il partizionamento sul posto. Questa partizione instabile richiede spazio O (1).
- Dopo il partizionamento, la partizione con il minor numero di elementi viene ordinata per prima (ricorsivamente), richiedendo al massimo spazio O (log n). Quindi laltra partizione viene ordinata utilizzando la ricorsione o literazione della coda, che non si aggiunge allo stack di chiamate. Questa idea, come discusso sopra, è stata descritta da R. Sedgewick e mantiene la profondità dello stack limitata da O (log n).