A gyorsrendezés elemzése

Mi az oka annak, hogy a gyorsrendezés legrosszabb esetben mért és átlagos esetben mért futásideje különbözik? Kezdjük azzal, hogy megvizsgáljuk a legrosszabb esetet. Tegyük fel, hogy olyan pechesek vagyunk, hogy a partíciók mérete nagyon egyenetlen. Például tegyük fel, hogy a partition függvény által választott vezérelem mindig az $n$‍-elemű résztömbnek vagy a legkisebb, vagy a legnagyobb eleme. Ekkor az egyik partíciónak nem lesz eleme, a másiknak viszont $n-1$‍ eleme lesz – az összes elem a vezérelemtől eltekintve. Így a rekurzív hívások 0 és $n-1$‍ hosszúságú résztömbökre fognak vonatkozni..

Az összefésülő rendezéshez hasonlóan $n$‍-elemű résztömbre vonatkozóan egy rekurzív hívás futásideje $\mathrm{\Theta }(n)$‍. Az összefésülő rendezés esetében ez az összefésülés idejére vonatkozik, a gyorsrendezésnél ez a particionálás futásideje.

Amikor a gyorsrendezés partíciói a lehető legegyenetlenebbek, akkor az eredeti hívás futásideje $cn$‍ egy adott $c$‍ konstans mellett, a rekurzív hívás $n-1$‍ elemre $c(n-1)$‍ lesz, a rekurzív hívás $n-2$‍ elemre $c(n-2)$‍ lesz, és így tovább. Az alábbi fa mutatja a részfeladatok méretét és az azokhoz tartozó particionálási időket:

Ha összeadjuk az összes szint particionálási idejét, ezt kapjuk:

Az utolsó sor magyarázata: $1+2+3+\cdots +n$‍ egy számtani sorozat, amint azt a minimumkiválasztásos rendezés elemzése során láttuk. (Levonunk belőle 1-et, mert a gyorsrendezésnél az összegzés 2-vel kezdődik, nem 1-gyel.) Van néhány alacsonyabb szintű tag és konstans együttható, ezeket elhanyagoljuk. A Θ jelölés alapján a gyorsrendezés futásideje a legrosszabb esetben $\mathrm{\Theta }(n^2)$‍.

A gyorsrendezés legjobb esete az, amikor a partíciók a lehető legkiegyensúlyozottabbak: a partíciók mérete vagy egyenlő, vagy csak 1-gyel térnek el egymástól. Az első eset akkor fordul elő, ha a résztömb elemeinek száma páratlan, és a vezérelem a particionálás után pont középen helyezkedik el. Így minden partícióba $(n-1)/2$‍ elem kerül. A második eset akkor fordul elő, ha a résztömb elemeinek száma, $n$‍, páros, ekkor az egyik partíció mérete $n/2$‍, a másiké $n/2-1$‍ lesz. Mindkét esetben a partíciók elemszáma maximum $n/2$‍ lehet, és a részfeladatok méretét ábrázoló fa nagyon hasonló lesz az összefésülő rendezés részfeladataihoz készített fához, ahol a particionálási idők nagyon hasonlítanak az összefésülési időkre:

Θ jelöléssel ugyanazt kapjuk, mint az összefésülő rendezésnél: $\mathrm{\Theta }(n{\log }_{2}n)$‍.

Annak megmutatása, hogy az átlagos esetben is $\mathrm{\Theta }(n{\log }_{2}n)$‍ lesz a futásidő, bonyolult matematikai fejtegetést igényel, úgyhogy ettől itt most eltekintünk. De néhány példán keresztül szemléltethetjük, hogy miért lehet valóban $O(n{\log }_{2}n)$‍ a futásidő. (Ha látjuk, hogy $O(n{\log }_{2}n)$‍ igaz, akkor a $\mathrm{\Theta }(n{\log }_{2}n)$‍ korlát is igaz lesz, mert az átlagos futásidő nem lehet jobb, mint a legjobb eset futásideje.) Először tegyük fel, hogy nem mindig kapunk kiegyensúlyozott partíciókat, de a partícióink sohase lesznek rosszabbak az 1 a 3-hoz aránynál. Azaz minden particionálás alkalmával az egyik partícióba $3n/4$‍ elem, a másikba pedig $n/4$‍ elem kerül. (Azért, hogy a számítás egyszerű maradjon, itt most hagyjuk figyelmen kívül a vezérelemet.) Ekkor a részfeladatok fája és a particionálási idők így fognak kinézni:

Minden csomópont bal oldalán a részfeladat az eredeti 1/4-e, a jobb oldali pedig a 3/4-e. Mivel a kisebb részfeladatok a bal oldalon vannak, a bal oldali leszármazási utat követve a gyökértől az 1 hosszúságú részfeladatig gyorsabban jutunk el, mint bármelyik másik útvonalon. Mint ahogy az ábrán is látszik, ${\log }_{4}n$‍ szint után jutunk el az 1 hosszúságú részfeladathoz. Miért ${\log }_{4}n$‍ szint van? Talán könnyebb úgy gondolkodni, hogy elindulunk egy 1 hosszúságú részfeladattal, és addig szorozzuk 4-gyel, amíg eljutunk $n$‍-ig. Másképpen fogalmazva keressük azt az $x$‍ értéket, amire igaz, hogy $4^x=n$‍. Ennek a megoldása ${\log }_{4}n$‍. Mi van akkor, ha a jobb oldali leszármazási utat követjük? Az ábrából látszik, hogy ${\log }_{4/3}n$‍ szint kell, hogy elérjük az 1 hosszúságú részfeladatot. Miért ${\log }_{4/3}n$‍ szint kell? Mivel minden jobb oldali leszármazott a felette levőnek (a szülő csomópontnak) 3/4-e, minden szülő a jobb oldali leszármazott 4/3-szorosa. Megint induljunk az 1 hosszúságú részfeladattal, és szorozzuk meg 4/3-dal mindaddig, amíg elérjük $n$‍-t. Milyen $x$‍ értékre igaz $(4/3{)}^x=n$‍? A válasz ${\log }_{4/3}n$‍.

Az első ${\log }_{4}n$‍ szint mindegyikében $n$‍ elem van (itt is beleszámoljuk a vezérelemeket, amiket már nem particionálunk), így ezeknek a szinteknek a teljes particionálási ideje $cn$‍. De mi a helyzet a többi szinttel? Mindegyikben n elemnél kevesebb van, így a particionálási idő minden szintre maximum $cn$‍. Összesen ${\log }_{4/3}n$‍ szint van, így a teljes particionálási idő $O(n{\log }_{4/3}n)$‍. Az alábbi matematikai összefüggés alapján:

minden pozitív $a$‍, $b$‍ és $n$‍-re. Legyen $a=4/3$‍ és $b=2$‍, azt kapjuk, hogy

így ${\log }_{4/3}n$‍ és ${\log }_{2}n$‍ csak ${\log }_2(4/3)$‍-ben különböznek, ami viszont egy konstans. Mivel a konstans tényezők nem számítanak az O jelölésnél, azt mondhatjuk, hogy ha minden particionálás 3 az 1-hez történik, akkor a gyorsrendezés futási ideje $O(n{\log }_{2}n)$‍, bár itt a rejtett konstans tényező nagyobb, mint a legjobb eset futási idejénél.

Milyen gyakorisággal várható, hogy 3:1-es, vagy annál jobb felosztással fogunk találkozni? Attól függ, hogyan választjuk ki a vezérelemet. Tegyük fel, hogy a vezérelem particionálás után azonos valószínűséggel lehet bárhol az $n$‍-elemű résztömbben. Ahhoz, hogy 3:1-es vagy annál jobb felosztásunk legyen, a vezérelemnek valahol a résztömb „középső felébe” kell kerülnie.

Ha a vezérelem egyenlő valószínűséggel kerülhet bárhová a résztömbben a particionálást követően, 50% a valószínűsége annak, hogy legalább 3:1-es felosztást kapjunk, más szóval körülbelül az esetek felében 3:-1-es felosztást, vagy annál jobbat várhatunk.

Nézzük meg a másik esetet is, hogy megértsük, miért $O(n{\log }_{2}n)$‍ a gyorsrendezés átlagos futásideje, ha az esetek felében nem 3:1-es, hanem a legrosszabb esetnek megfelelő felosztást kapjuk. Tegyük fel, hogy a 3:1-es és a legrosszabb eset felváltva fordulnak elő. A fa csomópontjait tekintsd úgy, hogy azok $k$‍ elemű résztömböket jelentenek. Akkor a fa egy részlete így néz ki:

e helyett:

Ezért még akkor is, ha az esetek felében a legrosszabb felosztást kapjuk, a másik felében pedig 3:1-es vagy annál jobb felosztást, a futásidő körülbelül kétszerese lenne annak, amit akkor kapnánk, ha mindig 3:1-es felosztásunk lenne. Ez viszont megint csak egy konstans tényező, ami eltűnik az O jelölésben, úgyhogy ebben az esetben, amikor váltakozva kapunk legrosszabb, illetve 3:1-es felosztást, a futásidő $O(n{\log }_{2}n)$‍.

Ne feledd, a fenti nem precíz matematikai bizonyítás, de egy jól szemlélteti, hogy miért $O(n{\log }_{2}n)$‍ az átlagos futásidő.

Tegyük fel, hogy a legnagyobb ellenséged – tudván, hogy mindig a jobb szélső elemet választod vezérelemnek –, egy olyan tömböt ad neked, hogy gyorsrendezéssel rendezd, ami úgy van összeállítva, hogy mindig a legrosszabb felosztás jöjjön ki. Hogyan tudnád meghiúsítani a szándékát?

Megteheted azt is, hogy nem mindig a jobb szélső elemet választod minden résztömbben vezérelemnek. Ehelyett véletlenszerűen választod ki a vezérelemet a résztömb elemei közül. De álljunk meg egy percre – a partition függvény azt feltételezi, hogy a vezérelem a résztömb jobb szélén van. Nem baj, egyszerűen kicseréled a kiválasztott elemet és a jobb szélső elemet, és a szokásos módon particionálsz. Mindaddig, míg az ellenséged nem tudja, hogy hogyan választod ki a véletlen pozíciót, te nyersz!

Tulajdonképpen egy kis plusz munkával nagyobb esélyed lesz arra, hogy legrosszabb esetben 3:1-es felosztásod legyen. Ne egy, hanem három elemet válassz ki véletlenszerűen a tömbből, és válaszd a három elem mediánját vezérelemnek (és azt cseréld ki a jobb szélső elemmel). Medián alatt a három elem közül a középső értéket értjük. Itt most nem mutatjuk meg, hogy miért, de ha a három, véletlenszerűen kiválasztott elem mediánját választod vezérelemnek, akkor 68,75%-os valószínűséggel (11/16) kapsz 3:1-es vagy annál jobb felosztást. Még ennél is tovább mehetsz. Ha véletlenszerűen öt elemet választasz, és azoknak veszed a mediánját vezérelemnek, akkor a 3:1-es vagy jobb felosztás valószínűsége körülbelül 79,3%-ra javul (203/256). Ha hét véletlenszerűen kiválasztott elem mediánját veszed, a valószínűség 85,9%-ra (1759/2048) nő. Kilenc elem mediánja esetén mennyi lesz? Kb. 90,2% (59123/65536). 11 elem mediánja? Kb. 93,1% (488293/524288). Látszik a tendencia. Persze nem feltétlenül éri meg nagyszámú véletlen elemet kiválasztani a medián kiválasztásához, mert az erre fordított idő ellensúlyozhatja azt a hasznot, amit a jó felosztás valószínűségének növelésével elérhetünk.

Ez a fejezet a Dartmouth Computer Science két professzora, Thomas Cormen és Devin Balkcom, valamint a Khan Academy informatika tanmenetfejlesztő csapatának együttműködésében készült. A tartalom a CC-BY-NC-SA licenc alatt engedélyezett.