The Art of Machinery

Minden tisztességes algoritmus tankönyv elmagyarázza, hogy milyen gyorsak az olyan rendező algoritmusok, mint a quicksort és a heapsort, de nem kell őrült matematika annak bizonyításához, hogy ezek a lehető legszimptotikusabban gyorsak.

Egy pedáns megjegyzés a jelölésekről

A legtöbb informatikus a big-O jelölést úgy használja, hogy “aszimptotikusan egyenlő, egy konstans skálázási tényezőig”, ami nem egészen azt jelenti, amit más matematikusok számára. Sajnálom, a big-O-t úgy fogom használni, mint a CS tankönyvekben, de legalább nem keverem más matematikai jelölésekkel.

Összehasonlításon alapuló rendezés

Nézzük meg az olyan algoritmusok speciális esetét, amelyek egyszerre két értéket hasonlítanak össze (mint a quicksort és a heapsort, és a legtöbb más népszerű algoritmus). Az ötletek később kiterjeszthetők az összes rendezési algoritmusra.

Egy egyszerű számolási érv a legrosszabb esetre

Tegyük fel, hogy van egy négy elemet tartalmazó tömbünk, mindegyik különböző, véletlenszerű sorrendben. Tudod-e rendezni úgy, hogy csak az elemek egypárját hasonlítod össze? Nyilvánvalóan nem, de itt van egy jó ok, ami bizonyítja, hogy nem tudod: A definíció szerint a tömb rendezéséhez,hogyan kell átrendezni az elemeket, hogy sorrendbe rakd őket. Más szóval, tudnod kell, hogy melyik permutációra van szükség. Hány lehetséges permutáció létezik? Az első elemet a négy hely valamelyikére lehet áthelyezni, a másodikat a maradék három hely valamelyikére, a harmadik elemre két lehetőség van, és az utolsó elemnek a maradék helyre kell kerülnie. Tehát 4×3×2×1=4!=244 \times 3 \times 2 \times 1 = 4! = 24 lehetséges permutáció közül választhatunk, de két különböző dolog összehasonlításából csak két lehetséges eredmény adódik: “Nagyobb” és “Kisebb”. Ha készítenél egy listát az összes lehetséges permutációról, akkor eldönthetnéd, hogy a “NAGYABB” azt jelenti, hogy a 8-as permutációra van szükséged, a “KISEBB” pedig azt, hogy a 24-es permutációra, de nem tudhatod, hogy mikor van szükséged a másik 22 permutációra.

Két összehasonlítással 2×2=42 \times 2 = 4 lehetséges eredményed van, ami még mindig nem elég. Nem tudsz minden lehetséges kevert tömböt rendezni, hacsak nem csinálsz legalább öt összehasonlítást (25=322^5 = 32). Ha W(N)W(N) a legrosszabb esetben szükséges összehasonlítások száma az NN különböző elemek valamilyen algoritmus segítségével történő rendezéséhez, akkor azt mondhatjuk

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

A 2-es bázisú logaritmust véve,

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

Aszimptotikusan N!N! növekszik, mint NNN^N (lásd még Stirling formuláját), így

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

És ez egy O(NlogN)O(N\log N) határérték a legrosszabb esetben csak a kimenetek számolásából.

Általános eset az információelméletből

Egy erősebb eredményt kaphatunk, ha ezt a számolási érvet egy kis információelmélettel bővítjük. Íme, hogyan használhatnánk egy rendező algoritmust információátviteli kódként:

1. Gondolok egy számra – mondjuk 15
2. Keresem a 15. számú permutációt a négy elemű permutációk listájából
3. Futtatom a rendezési algoritmust ezen a permutáción, és feljegyzem az összes “NAGYOBB” és “KISEBB” összehasonlítási eredményt
4. Az összehasonlítási eredményeket bináris kódban továbbítom neked
5. Megismétled a rendezési algoritmus lefutását, lépésről lépésre, szükség szerint hivatkozva az összehasonlítási eredményeim listájára
6. Most, hogy tudod, hogyan rendeztem át a tömbömet, hogy rendezetté tegyem, megfordíthatod a permutációt, hogy kiderítsd az eredeti tömbömet
7. Megnézed az eredeti tömbömet a permutációs listában, hogy kiderítsd, a 15-ös számot továbbítottam

Oké, ez egy kicsit furcsa, de meg lehet csinálni. Ez azt jelenti, hogy a rendezési algoritmusokat ugyanazok a törvények kötik, mint a normális kódolási sémákat, beleértve azt a tételt, amely bizonyítja, hogy nincs univerzális adattömörítő. Az algoritmus által végzett összehasonlításonként egy bitet továbbítottam, tehát az információelmélet szerint az összehasonlítások számának átlagosan legalább annyi bitnek kell lennie, ahány bitre van szükség az adataim reprezentálásához. Technikailag az összehasonlítások átlagos számának legalább a bemeneti adataim bitekben mért Shannon-entrópiájának kell lennie. Az entrópia valaminek az információtartalmának vagy kiszámíthatatlanságának matematikai mérőszáma.

Ha van egy NN elemekből álló tömböm, amely torzítás nélkül bármilyen sorrendben állhat, akkor az entrópia maximális, és log2N!\log_2{N!} bit. Ez bizonyítja, hogy O(NlogN)O(N\log{N}) az optimális átlag egy összehasonlításon alapuló rendezéshez tetszőleges bemenettel.

Ez az elmélet, de hogyan viszonyulnak a valós rendezési algoritmusok? Az alábbiakban egy tömb rendezéséhez szükséges összehasonlítások átlagos számát ábrázoljuk. Összehasonlítottam az elméleti optimumot a naiv quicksorttal és a Ford-Johnson merge-insertion sorttal, amelyet az összehasonlítások minimalizálására terveztek (bár összességében ritkán gyorsabb, mint a quicksort, mert az élet többről szól, mint az összehasonlítások minimalizálása). 1959-es kifejlesztése óta a merge-insertion sortot finomították, hogy még néhány összehasonlítást kicsikarjanak belőle, de a grafikon szerint már majdnem optimális.

Nagyon jó, amikor egy kis elmélet ilyen szoros gyakorlati eredményt ad.

Az eddigi összefoglaló

Itt van, amit eddig bebizonyítottunk:

1. Ha a tömb tetszőleges sorrendben indulhat, akkor legrosszabb esetben is legalább O(NlogN)O(N\log{N}) összehasonlításra van szükség
2. Az összehasonlítások átlagos számának legalább a tömb entrópiájának kell lennie, ami O(NlogN)O(N\log{N}) véletlenszerű bemenet esetén

Megjegyezzük, hogy a #2 lehetővé teszi, hogy az összehasonlításon alapuló rendezési algoritmusok gyorsabbak legyenek O(NlogN)O(N\log{N})-nál, ha a bemenet alacsony entrópiájú (más szóval, jobban kiszámítható). Az egyesítéses rendezés közel O(N)O(N), ha a bemenet sok rendezett altáblát tartalmaz. A beillesztési rendezés közel O(N)O(N), ha a bemenet egy olyan tömb, amelyet a perturbálás előtt rendeztünk egy kicsit. Egyik sem veri megO(NlogN)O(N\log{N}) a legrosszabb esetben, kivéve, ha bizonyos tömbrendezések lehetetlenek bemenetként.

Általános rendező algoritmusok

A gyakorlatban érdekes speciális eset az összehasonlításon alapuló rendezés, de elméletileg semmi különleges nincs benneCMP a számítógép bármely más utasításával szemben. Mindkét fenti érv általánosítható bármely rendező algoritmusra, ha megjegyzünk néhány dolgot:

1. A legtöbb számítógépes utasításnak kettőnél több lehetséges kimenete van, de még így is korlátozott számú
2. A kimenetek korlátozott száma azt jelenti, hogy egy utasítás csak korlátozott mennyiségű entrópiát tud feldolgozni

Ez ugyanazt az O(NlogN)O(N\log{N}) alsó korlátot adja az utasítások számára. Bármely fizikailag megvalósítható számítógép egyszerre csak korlátozott számú utasítást tud feldolgozni, így ez egy O(NlogN)O(N\log{N}) alsó korlátot jelent a szükséges időre is.

De mi a helyzet a “gyorsabb” algoritmusokkal?

Az általános O(NlogN)O(N\log{N}) korlát leghasznosabb gyakorlati következménye az, hogy ha hallunk bármilyen aszimptotikusan gyorsabb algoritmusról, akkor tudjuk, hogy az valahogy “csal”. Kell lennie valami csapdának, ami azt jelenti, hogy ez nem egy általános célú rendező algoritmus, amely tetszőlegesen nagy tömbökre skálázódik. Ettől még lehet, hogy hasznos algoritmus, de jó ötlet alaposan elolvasni az apró betűs részt.

Egy jól ismert példa a radix rendezés. Gyakran nevezik O(N)O(N) rendező algoritmusnak, de a bökkenő az, hogy csak akkor működik, ha minden szám belefér kk bitbe, és valójában O(kN)O(kN).

Mit jelent ez a gyakorlatban? Tegyük fel, hogy van egy 8 bites géped. 8 bitben 28=2562^8 = 256 különböző számot tudsz ábrázolni, tehát ha egy több ezer számból álló tömböd van, akkor duplikátumokkal fogsz rendelkezni. Ez bizonyos alkalmazásokhoz rendben lehet, de másokhoz legalább 16 bitesre kell fejleszteni, amely 216=65,5362^16 = 65,536 számot képes megkülönböztethetően ábrázolni. A 32 bites számok 232=4,294,967,2962^32 = 4,294,967,296 különböző számot támogatnak. Ahogy nő a tömb mérete, úgy nő a szükséges bitek száma is. Az NN különböző számok megkülönböztethető ábrázolásához k≥log2Nk \geq \log_2{N} szükséges. Tehát, hacsak nincs rendben a sok duplikátum a tömbben, az O(kN)O(kN) gyakorlatilag O(NlogN)O(N\log{N}).

Az, hogy az általános esetben O(NlogN)O(N\log{N}) bemeneti adatra van szükség, tulajdonképpen önmagában is bizonyítja az általános eredményt. Ez az érv a gyakorlatban nem annyira érdekes, mert ritkán kell több milliárd egész számot rendezni egy 32 bites gépen, és ha valaki elérte a 64 bites gép határait, azt nem mondta el a többieknek.