Fő tartalom
Számítástudomány
Tantárgy/kurzus: Számítástudomány > 1. témakör
9. lecke: GyorsrendezésA 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 -elemű résztömbnek vagy a legkisebb, vagy a legnagyobb eleme. Ekkor az egyik partíciónak nem lesz eleme, a másiknak viszont eleme lesz – az összes elem a vezérelemtől eltekintve. Így a rekurzív hívások 0 és hosszúságú résztömbökre fognak vonatkozni..
partition
függvény által választott vezérelem mindig az Az összefésülő rendezéshez hasonlóan -elemű résztömbre vonatkozóan egy rekurzív hívás futásideje . 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.
A legrosszabb eset futásideje
Amikor a gyorsrendezés partíciói a lehető legegyenetlenebbek, akkor az eredeti hívás futásideje egy adott konstans mellett, a rekurzív hívás elemre lesz, a rekurzív hívás elemre 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: 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 .
A legjobb eset futásideje
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 elem kerül. A második eset akkor fordul elő, ha a résztömb elemeinek száma, , páros, ekkor az egyik partíció mérete , a másiké lesz. Mindkét esetben a partíciók elemszáma maximum 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: .
Az átlagos eset futásideje
Annak megmutatása, hogy az átlagos esetben is 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 a futásidő. (Ha látjuk, hogy igaz, akkor a 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 elem, a másikba pedig 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, szint után jutunk el az 1 hosszúságú részfeladathoz. Miért 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 -ig. Másképpen fogalmazva keressük azt az értéket, amire igaz, hogy . Ennek a megoldása . Mi van akkor, ha a jobb oldali leszármazási utat követjük? Az ábrából látszik, hogy szint kell, hogy elérjük az 1 hosszúságú részfeladatot. Miért 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 -t. Milyen értékre igaz ? A válasz .
Az első szint mindegyikében 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 . De mi a helyzet a többi szinttel? Mindegyikben . Összesen szint van, így a teljes particionálási idő . Az alábbi matematikai összefüggés alapján:
n
elemnél kevesebb van, így a particionálási idő minden szintre maximum minden pozitív , és -re. Legyen és , azt kapjuk, hogy
így és csak -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 , 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 -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 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 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ő .
Ne feledd, a fenti nem precíz matematikai bizonyítás, de egy jól szemlélteti, hogy miért az átlagos futásidő.
Randomizált gyorsrendezés
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.
Szeretnél részt venni a beszélgetésben?
Még nincs hozzászólás.