Qual è la complessità temporale dellordinamento rapido?

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.

  1. Scegli sempre il primo elemento come pivot.
  2. Scegli sempre lultimo elemento come pivot (implementato sotto)
  3. Scegli un elemento casuale come pivot.
  4. 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).

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *