Care manual de algoritmi decent va explica cât de rapizi sunt algoritmii de sortare precum quicksort și heapsort, dar nu este nevoie de o matematică nebună pentru a dovedi că aceștia sunt cât se poate de rapizi asimptotic.
O notă pedantă despre notație
Majoritatea informaticienilor folosesc notația big-O pentru a însemna „asimptotic egal, până la un factor de scalare constant”, ceea ce nu este chiar ceea ce înseamnă pentru alți matematicieni. Îmi pare rău, voi folosi big-O ca în manualele de CS, dar cel puțin nu o voi amesteca cu alte notații matematice.
Sortare bazată pe comparație
Să ne uităm la cazul special al algoritmilor care compară valorile două câte două (cum ar fi quicksort și heapsort, și majoritatea celorlalți algoritmi populari). Ideile pot fi extinse ulterior la toți algoritmii de sortare.
Un argument simplu de numărare pentru cazul cel mai defavorabil
Să presupunem că aveți un array de patru elemente, toate diferite, în ordine aleatorie. Îl puteți sorta comparând doar o singură pereche de elemente? Evident că nu, dar iată un motiv bun care dovedește că nu se poate: prin definiție, pentru a sorta array-ul,trebuie să cum să rearanjezi elementele pentru a le pune în ordine. Cu alte cuvinte, trebuie să știi ce permutare este necesară. Câte permutări posibile există? Primul element poate fi mutat într-unul din cele patru locuri, al doilea poate fi mutat într-unul din cele trei rămase, al treilea element are două opțiuni, iar ultimul element trebuie să ocupe singurul loc rămas. Așadar, există 4×3×2×1×1=4!=244 \înmulțit cu 3 \înmulțit cu 2 \înmulțit cu 1 = 4! = 24 de permutări posibile din care se poate alege, dar există doar două rezultate posibile din compararea a două lucruri diferite: „MAI MARE” și „MAI MIC”. Dacă ați face o listă cu toate permutările posibile, ați putea decide că „MAI MARE” înseamnă că aveți nevoie de permutarea nr. 8 și „MAI MICĂ” înseamnă că aveți nevoie de permutarea nr. 24, dar nu aveți cum să știți când aveți nevoie de celelalte 22 de permutări.
Cu două comparații, aveți 2×2=42 \înmulțit cu 2 = 4 rezultate posibile, ceea ce tot nu este suficient. Nu puteți sorta fiecare tablou amestecat posibil decât dacă faceți cel puțin cinci comparații (25=322^5 = 32). Dacă W(N)W(N) este cel mai rău caz numărul de comparații necesare pentru a sorta NN elemente diferite folosind un anumit algoritm, putem spune
2W(N)≥N!2^{W(N)} \geq N!
Plecând de la un logaritm de bază 2,
W(N)≥log2N!W(N) \geq \log_2{N!}
Asimptotic, N!N! crește ca NNN^N (a se vedea, de asemenea, formula lui Stirling), deci
W(N)⪰logNN=NlogNW(N) \succeq \log{N^N} = N\log{N}
Și aceasta este o limită O(NlogN)O(N\log N) în cel mai rău caz doar din numărarea ieșirilor.
Cazul mediu din teoria informației
Am putea obține un rezultat mai puternic dacă extindem acest argument de numărare cu puțină teorie a informației. Iată cum am putea folosi un algoritm de sortare ca un cod pentru transmiterea de informații:
- Mă gândesc la un număr – să zicem, 15
- Căutăm permutarea #15 din lista de permutări a patru elemente
- Executăm algoritmul de sortare pe această permutare și înregistrăm toate rezultatele comparației „MAI MARE” și „MAI MICĂ”
- Vă transmit rezultatele comparației în cod binar
- Voi redați execuția algoritmului meu de sortare, pas cu pas, referindu-vă la lista mea de rezultate ale comparației, după cum este necesar
- Acum că știți cum mi-am rearanjat matricea pentru a o sorta, puteți inversa permutarea pentru a afla matricea mea originală
- Vă uitați la matricea mea originală în lista de permutări pentru a vă da seama că am transmis numărul 15
Ok, este puțin ciudat, dar se poate face. Asta înseamnă că algoritmii de sortare sunt legați de aceleași legi ca și schemele normale de codificare, inclusiv de teorema care dovedește că nu există un compresor universal de date. Am transmis un bit pentru fiecare comparație pe care o face algoritmul, deci, în medie, numărul de comparații trebuie să fie cel puțin numărul de biți necesari pentru a reprezenta datele mele, conform teoriei informației. Mai tehnic, numărul mediu de comparații trebuie să fie cel puțin entropia Shannon a datelor mele de intrare, măsurată în biți. Entropia este o măsură matematică a conținutului informațional, sau a imprevizibilității, a ceva.
Dacă am o matrice de NN elemente care ar putea fi în orice ordine posibilă fără a fi părtinitoare, atunci entropia este maximizată și estelog2N!\log_2{N!} biți. Asta dovedește că O(NlogN)O(N\log{N}) este o medie optimă pentru o sortare bazată pe comparație cu intrare arbitrară.
Aceasta este teoria, dar cum se compară algoritmii reali de sortare? Mai jos este un grafic al numărului mediu de comparațiinecesare pentru a sorta o matrice. Am comparat optimul teoretic cu quicksort naiv și cu sortarea Ford-Johnson de fuziune-inserție, care a fost conceput pentru a minimiza comparațiile (deși este rareori mai rapid decât quicksort în general, deoarece există mai multe lucruri în viață decât minimizarea comparațiilor). De când a fost dezvoltat în 1959, sortarea prin îmbinare-inserție a fost modificată pentru a scoate câteva comparații în plus, dar graficul arată că este deja aproape optimă.
Este frumos când puțină teorie oferă un rezultat practic atât de strâns.
Rezumat până acum
Iată ce s-a dovedit până acum:
- Dacă matricea ar putea începe în orice ordine, sunt necesare cel puțin O(NlogN)O(N\log{N}) comparații în cel mai rău caz
- Numărul mediu de comparații trebuie să fie cel puțin entropia matricei, care este O(NlogN)O(N\log{N}) pentru o intrare aleatorie
Rețineți că #2 permite algoritmilor de sortare pe bază de comparații să fie mai rapizi decât O(NlogN)O(N\log{N}) dacă intrarea este cu entropie scăzută (cu alte cuvinte, mai previzibilă). Sortarea combinată este aproape de O(N)O(N) dacă datele de intrare conțin multe subrețele sortate. Sortarea prin inserție este apropiată de O(N)O(N) dacă intrarea este o matrice care a fost sortată înainte de a fi puțin perturbată. Niciunul dintre ei nu bateO(NlogN)O(N\log{N}) în cel mai rău caz, cu excepția cazului în care unele ordonări de array-uri sunt imposibile ca intrări.
Algoritmi generali de sortare
Sortarea bazată pe comparație este un caz special interesant în practică, dar nu există nimic special din punct de vedere teoretic despreCMP față de orice altă instrucțiune de pe un calculator. Ambele argumentede mai sus pot fi generalizate la orice algoritm de sortare, dacă observați câteva lucruri:
- Majoritatea instrucțiunilor de calculator au mai mult de două ieșiri posibile, dar au totuși un număr limitat
- Numărul limitat de ieșiri înseamnă că o instrucțiune poate procesa doar o cantitate limitată de entropie
Acesta ne dă aceeași limită inferioară O(NlogN)O(N\log{N}) pentru numărul de instrucțiuni. Orice calculator realizabil din punct de vedere fizic poate procesa doar un număr limitat de instrucțiuni la un moment dat, astfel încât aceasta este o limită inferioară O(NlogN)O(N\log{N}) și pentru timpul necesar.
Dar cum rămâne cu algoritmii „mai rapizi”?
Cea mai utilă implicație practică a limitei generale O(NlogN)O(N\log{N}) este că, dacă auziți despre orice algoritm asimptotic mai rapid, știți că trebuie să „trișeze” cumva. Trebuie să existe o capcană care să însemne că nu este un algoritm de sortare de uz general care se adaptează la matrici arbitrar de mari dimensiuni. S-ar putea să fie în continuare un algoritm util, dar este o idee bună să citiți cu atenție literele mici.
Un exemplu bine cunoscut este sortarea radix. Este deseori numit un algoritm de sortare O(N)O(N), dar problema este că funcționează doar dacă toate numerele încap în kk biți, iar în realitate este O(kN)O(kN).
Ce înseamnă asta în practică? Să presupunem că aveți o mașină pe 8 biți. Puteți reprezenta 28=2562^8 = 256 de numere diferite în 8 biți, astfel încât, dacă aveți o matrice de mii de numere, veți avea duplicate. Acest lucru ar putea fi în regulă pentru unele aplicații, dar pentru altele trebuie să treceți la cel puțin 16 biți, care pot reprezenta 216=65.5362^16 = 65.536 numere în mod distinct. 32 de biți vor suporta 232=4,294,967,2962^32 = 4,294,967,296 numere diferite. Pe măsură ce dimensiunea matricei crește, numărul de biți necesari va avea tendința de a crește și el. Pentru a reprezenta în mod distinct NN numere diferite, veți avea nevoie de k≥log2Nk \geq \log_2{N}. Deci, dacă nu sunteți de acord cu o mulțime de duplicate în matricea dvs., O(kN)O(kN) este de fapt O(NlogN)O(N\log{N}).
Nevoia de O(NlogN)O(N\log{N}) de date de intrare în cazul general dovedește de fapt rezultatul general de la sine. Acest argument nu este atât de interesant în practică, deoarece rareori avem nevoie să sortăm miliarde de numere întregi pe o mașină pe 32 de biți, iar dacă cineva a atins limitele unei mașini pe 64 de biți, nu ne-a spus celorlalți.
.