If you're seeing this message, it means we're having trouble loading external resources on our website.

Ha webszűrőt használsz, győződj meg róla, hogy a *.kastatic.org és a *.kasandbox.org nincsenek blokkolva.

Fő tartalom

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 n1 eleme lesz – az összes elem a vezérelemtől eltekintve. Így a rekurzív hívások 0 és n1 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 Θ(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.

A legrosszabb eset 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 n1 elemre c(n1) lesz, a rekurzív hívás n2 elemre c(n2) 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:
cn+c(n1)+c(n2)++2c=c(n+(n1)+(n2)++2)=c((n+1)(n/2)1) .
Az utolsó sor magyarázata: 1+2+3++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 Θ(n2).

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 (n1)/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/21 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: Θ(nlog2n).

Az átlagos eset futásideje

Annak megmutatása, hogy az átlagos esetben is Θ(nlog2n) 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(nlog2n) a futásidő. (Ha látjuk, hogy O(nlog2n) igaz, akkor a Θ(nlog2n) 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, log4n szint után jutunk el az 1 hosszúságú részfeladathoz. Miért log4n 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 4x=n. Ennek a megoldása log4n. Mi van akkor, ha a jobb oldali leszármazási utat követjük? Az ábrából látszik, hogy log4/3n szint kell, hogy elérjük az 1 hosszúságú részfeladatot. Miért log4/3n 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 log4/3n.
Az első log4n 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 log4/3n szint van, így a teljes particionálási idő O(nlog4/3n). Az alábbi matematikai összefüggés alapján:
logan=logbnlogba
minden pozitív a, b és n-re. Legyen a=4/3 és b=2, azt kapjuk, hogy
log4/3n=log2nlog2(4/3) ,
így log4/3n és log2n csak log2(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(nlog2n), 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(nlog2n) 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(nlog2n).
Ne feledd, a fenti nem precíz matematikai bizonyítás, de egy jól szemlélteti, hogy miért O(nlog2n) 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.
Tudsz angolul? Kattints ide, ha meg szeretnéd nézni, milyen beszélgetések folynak a Khan Academy angol nyelvű oldalán.