Stavo esaminando i video delle conferenze di Robert Sedgwick sugli algoritmi, e spiega che il rimescolamento casuale ci assicura di non incontrare lo scenario temporale quadratico peggiore nell'ordinamento rapido. Ma non sono in grado di capire come.In che modo lo shuffling casuale nell'ordinamento rapido aiuta ad aumentare l'efficienza del codice?
Il presupposto è che il caso peggiore - tutto già risolto - è abbastanza frequente da meritare di essere preoccupato, e un rimescolamento è un modo sciatto black-magic con il minimo sforzo per evitare quel caso senza dover ammettere che di migliorando il caso in cui stai spostando il problema a un altro, che è capitato di mescolare casualmente nell'ordine ordinato. Speriamo che il caso negativo sia una situazione molto più rara, e anche se emerge la casualità significa che il problema non può essere facilmente riprodotto e incolpato di questo cheat.
Il concetto di migliorare un caso comune a scapito di uno raro va bene. La casualità come alternativa al pensare realmente a quali casi saranno più o meno comuni è alquanto sciatta.
Che cosa fa un casuale casuale alla distribuzione nello spazio di input? Per capire questo, diamo un'occhiata a una distribuzione di probabilità, P, definita su un set S, dove P non è sotto il nostro controllo. Creiamo una distribuzione di probabilità P' applicando un casuale shuffle, su S a P. In altre parole, ogni volta che otteniamo un campione da P, lo mappiamo, in modo uniforme a caso su un elemento di S. Cosa puoi dire di questa distribuzione risultante P'?
P'(x) = summation over all elements s in S of P(s)*1/|S| = 1/|S|
Così, P' è solo la distribuzione uniforme su S. Un casuale shuffle ci dà il controllo sulla distribuzione della probabilità di input.
Quanto è importante per quicksort? Bene, conosciamo la complessità media di quicksort. Questo è calcolato sulla distribuzione di probabilità uniforme e questa è una proprietà che vogliamo mantenere sulla nostra distribuzione di input, indipendentemente da cosa sia realmente. Per riuscirci, facciamo uno shuffle casuale del nostro array di input, assicurandoci che la distribuzione non sia contraddittoria in alcun modo.
È davvero un'ammissione che, anche se parliamo spesso della complessità media del caso, non ci aspettiamo in pratica che ogni caso si presenti con la stessa probabilità.
L'ordinamento di una matrice già ordinata è il caso peggiore in quicksort, perché ogni volta che si seleziona un pivot, si scopre che tutti gli elementi vengono posizionati sullo stesso lato del pivot, quindi non si suddividono in due metà approssimativamente uguali a tutti. E spesso nella pratica questo caso già risolto si presenta più spesso di altri casi.
Il rimescolamento casuale dei dati è un modo rapido per assicurarti di finire con tutti i casi che si presentano con uguale probabilità, e quindi che questo caso peggiore sarà raro come in tutti gli altri casi.
Vale la pena notare che esistono altre strategie che si adattano bene ai dati già ordinati, come la scelta dell'elemento centrale come pivot.
Il video è coursera? Sfortunatamente, shufflediminuire prestazioni su O (N^2) con dati n, n, ..., n, 1,1, ..., 1. Ho ispezionato Quick.java con nn11.awk che genera tali dati.
$ for N in 10000 20000 30000 40000; do time ./nn11.awk $N | java Quick; done | awk 'NF>1'
real 0m10.732s
user 0m10.295s
sys 0m0.948s
real 0m48.057s
user 0m44.968s
sys 0m3.193s
real 1m52.109s
user 1m48.158s
sys 0m3.634s
real 3m38.336s
user 3m31.475s
sys 0m6.253s
Un sacco di shuffle che girano in O (n) –
Shuffles non è essenziale. n, n, .., n, 1,1, ..., 1 viene mischiato al probabile andamento a zigzag. Anche se i dati n, 1, n, 1, ..., n, 1, n non sono mescolati, la complessità temporale di Quick.java è O (N^2). –
Mi dispiace. È stato risolto da QuickX.java. –
In caso di randomizzato QuickSort, poiché l'elemento a perno è scelto a caso, ci si può aspettare la scissione della matrice di input per essere ben bilanciata mediamente - contrariamente al caso di 1 e (n -1) diviso in una versione non randomizzata dell'algoritmo. Questo aiuta a prevenire il comportamento nel caso peggiore di QuickSort che si verifica nel partizionamento sbilanciato.
Quindi, il tempo medio di esecuzione del caso della versione randomizzata di QuickSort è O (nlogn) e non O (n^2);
Le lezioni di Robert Sedgewick sono davvero utili, sono facili da capire e poi utilizzate nella pratica. – QtRoS
Sono facili da capire Sono d'accordo, e tutto ciò che ho detto è che non sono in grado di capirlo. –