The Art of Machinery

Varje anständig lärobok om algoritmer förklarar hur snabba sorteringsalgoritmer som quicksort och heapsort är, men det krävs ingen galen matematik för att bevisa att de är så asymptotiskt snabba som möjligt.

En pedantisk anmärkning om notation

De flesta datavetare använder big-O notation för att betyda ”asymptotiskt lika, upp till en konstant skalningsfaktor”, vilket inte riktigt är vad det betyder för andra matematiker. Ledsen, jag kommer att använda big-O som i läroböcker i datavetenskap, men jag kommer åtminstone inte att blanda ihop det med annan matematisk notation.

Sortering baserad på jämförelser

Låt oss titta på specialfallet med algoritmer som jämför värden två i taget (som quicksort och heapsort, och de flesta andra populära algoritmer). Idéerna kan senare utvidgas till alla sorteringsalgoritmer.

Ett enkelt räkneargument för det värsta fallet

Antag att du har en array med fyra element, alla olika, i slumpmässig ordning. Kan du sortera den genom att bara jämföra ett par element? Uppenbarligen inte, men här är ett bra skäl som bevisar att det inte går: För att sortera matrisen måste du definitionsmässigt ordna om elementen för att sätta dem i ordning. Med andra ord måste du veta vilken permutation som behövs. Hur många möjliga permutationer finns det? Det första elementet kan flyttas till en av fyra platser, det andra elementet kan flyttas till en av de tre återstående platserna, det tredje elementet har två alternativ och det sista elementet måste ta den enda återstående platsen. Det finns alltså 4×3×2×1=4!=244 \times 3 \times 2 \times 1 = 4! = 24 möjliga permutationer att välja mellan, men det finns bara två möjliga resultat av att jämföra två olika saker: ”Större” och ”Mindre”. Om du gör en lista över alla möjliga permutationer kan du bestämma dig för att ”STÖRRE” innebär att du behöver permutation nr 8 och ”Mindre” innebär att du behöver permutation nr 24, men det finns inget sätt för dig att veta när du behöver de andra 22 permutationerna.

Med två jämförelser har du 2×2=42 \ gånger 2 = 4 möjliga utfall, vilket fortfarande inte är tillräckligt. Du kan inte sortera alla möjliga blandade matriser om du inte gör minst fem jämförelser (25=322^5 = 32). Om W(N)W(N) är det värsta antalet jämförelser som behövs för att sortera NN olika element med hjälp av någon algoritm, kan vi säga

2W(N)≥N!2^{W(N)} \geq N!

Om man tar en logaritm med bas 2,

W(N)≥log2N!W(N) \geq \log_2{N!}

Asymptotiskt sett blir N!N! växer som NNNN^N (se även Stirlings formel), så

W(N)⪰logNN=NlogNW(N) \succeq \log{N^N} = N\log{N}

O(NlogN)O(N\log N) är en O(NlogN)O(N\log N)-gräns för det värsta fallet bara genom att räkna utgångar.

Genomsnittligt fall från informationsteori

Vi kan få ett starkare resultat om vi utökar detta räkneargument med lite informationsteori. Här är hur vi skulle kunna använda en sorteringsalgoritm som en kod för överföring av information:

1. Jag tänker på ett tal – låt oss säga 15
2. Jag slår upp permutation nr 15 i listan över permutationer av fyra element
3. Jag kör sorteringsalgoritmen på denna permutation och registrerar alla jämförelseresultat för ”STÖRRE” och ”MINSKARE”
4. Jag överför jämförelseresultaten till dig i binär kod
5. Du återskapar min sorteringsalgoritmkörning, steg för steg, med hänvisning till min lista över jämförelseresultat vid behov
6. Nu när du vet hur jag ordnade om min matris för att få den sorterad, kan du vända på permutationen för att ta reda på min ursprungliga matris
7. Du slår upp min ursprungliga matris i permutationslistan för att ta reda på att jag överförde siffran 15

Okej, det är lite konstigt, men det går att göra. Det betyder att sorteringsalgoritmer är bundna av samma lagar somnormala kodningssystem, inklusive satsen som bevisar att det inte finns någon universell datakompressor. Jag överförde en bit per jämförelse som algoritmen gör, så i genomsnitt måste antalet jämförelser vara minst lika många bitar som behövs för att representera mina data, enligt informationsteorin. Mer tekniskt sett måste det genomsnittliga antalet jämförelser vara minst lika stort som Shannon-entropin hos mina indata, mätt i bitar. Entropi är ett matematiskt mått på informationsinnehållet, eller oförutsägbarheten, hos något.

Om jag har en matris med NN element som kan vara i vilken ordning som helst utan förskjutning som helst, är entropin maximerad och ärlog2N!\log_2{N!} bitar. Det bevisar att O(NlogN)O(N\log{N}) är ett optimalt medelvärde för en jämförelsebaserad sortering med godtycklig indata.

Det är teorin, men hur förhåller sig verkliga sorteringsalgoritmer till varandra? Nedan visas en graf av det genomsnittliga antalet jämförelser som behövs för att sortera en matris. Jag har jämfört det teoretiska optimumet med naiv quicksort och Ford-Johnson merge-insertion sort, som utformades för att minimera jämförelser (även om den sällan är snabbare än quicksort totalt sett eftersom det finns mer i livet än att minimera jämförelser). Sedan den utvecklades 1959 har merge-insertion sort ändrats för att få ut några fler jämförelser, men diagrammet visar att den redan är nästan optimal.

Det är trevligt när lite teori ger ett så bra praktiskt resultat.

Sammanfattning hittills

Här är vad som har bevisats hittills:

1. Om matrisen kan börja i vilken ordning som helst behövs minst O(NlogN)O(N\log{N}) jämförelser i värsta fall
2. Det genomsnittliga antalet jämförelser måste vara minst matrisens entropi, vilket är O(NlogN)O(N\log{N}) för slumpmässig indata

Notera att nr 2 gör det möjligt för jämförelsebaserade sorteringsalgoritmer att vara snabbare än O(NlogN)O(N\log{N}) om indatan har låg entropi (med andra ord är mer förutsägbar). Merge sort är nära O(N)O(N) om indata innehåller många sorterade subarrangemang. Insertion sort är nära O(N)O(N) om indata är en matris som var sorterad innan den stördes lite. Ingen av dem slårO(NlogN)O(N\log{N}) i värsta fall om inte vissa array-ordningar är omöjliga som indata.

Allmänna sorteringsalgoritmer

Samtalsbaserade sorteringsalgoritmer är ett intressant specialfall i praktiken, men det finns inget teoretiskt speciellt medCMP i motsats till någon annan instruktion på en dator. Båda argumenten ovan kan generaliseras till vilken sorteringsalgoritm som helst om man noterar ett par saker:

1. De flesta datorinstruktioner har mer än två möjliga utgångar, men har ändå ett begränsat antal
2. Det begränsade antalet utgångar innebär att en instruktion endast kan bearbeta en begränsad mängd entropi

Det ger oss samma O(NlogN)O(N\log{N})-nedre gräns på antalet instruktioner. Varje fysiskt realiserbar dator kan bara bearbeta ett begränsat antal instruktioner åt gången, så det är också en O(NlogN)O(N\log{N}) nedre gräns för den tid som krävs.

Men hur är det med ”snabbare” algoritmer?

Den mest användbara praktiska innebörden av den allmänna gränsen för O(NlogN)O(N\log{N}) är att om man hör talas om en asymtomatiskt snabbare algoritm, så vet man att den måste vara ”fuskande” på något sätt. Det måste finnas någon fälla som gör att det inte är en allmännyttig sorteringsalgoritm som kan skalas till godtyckligt stora matriser. Det kan fortfarande vara en användbar algoritm, men det är en bra idé att läsa det finstilta noga.

Ett välkänt exempel är radixsortering. Den kallas ofta för en O(N)O(N)-sorteringsalgoritm, men haken är att den bara fungerar om alla siffror ryms på kk bitar, och den är egentligen O(kN)O(kN).

Vad betyder det i praktiken? Anta att du har en 8-bitarsmaskin. Du kan representera 28=2562^8 = 256 olika tal på 8 bitar, så om du har en matris med tusentals tal kommer du att hauplicates. Det kan vara okej för vissa tillämpningar, men för andra tillämpningar måste du uppgradera till minst 16 bitar, som kan representera 216=65,5362^16=65,536 tal på ett distinkt sätt. 32 bitar stöder 232=4,294,967,2962^32 = 4,294,967,296 olika nummer. När storleken på matrisen ökar tenderar antalet nödvändiga bitar också att öka. För att representera NN olika tal på ett tydligt sätt behövs k≥log2Nk \geq \log_2{N}. Så om du inte är okej med många dubbletter i din matris är O(kN)O(kN) i praktiken O(NlogN)O(N\log{N}).

Behovet av O(NlogN)O(N\log{N}) av indata i det allmänna fallet bevisar faktiskt det övergripande resultatet i sig självt. Det argumentet är inte så intressant i praktiken eftersom vi sällan behöver sortera miljarder heltal på en 32-bitarsmaskin, och om någon har nått gränsen för en 64-bitarsmaskin har de inte berättat det för oss andra.