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

Oszd meg és uralkodj algoritmusok

Az eddig látott két rendező algoritmus, a minimumkiválasztásos rendezés és a beszúró rendezés legrosszabb futási ideje Θ(n2). Nagyméretű input tömb esetén ezeknek az algoritmusoknak hosszú lehet a futási idejük. Ebben és a következő fejezetben két másik rendezési algoritmust veszünk górcső alá, az összefésülő rendezést és a gyorsrendezést, amiknek jobb a futási idejük. Az összefésülő rendezés minden esetben Θ(nlgn) idő alatt fut le, a gyorsrendezés futási ideje a legjobb esetben, valamint átlagosan Θ(nlgn), viszont a legrosszabb esetben Θ(n2). Az alábbi táblázatban összefoglaltuk e négy rendezési algoritmus futási idejét a legjobb, az átlagos és a legrosszabb esetben:
AlgoritmusLegrosszabb futási időLegjobb futási időÁtlagos futási idő
Minimumkiválasztásos rendezésΘ(n2)Θ(n2)Θ(n2)
Beszúró rendezésΘ(n2)Θ(n)Θ(n2)
Összefésülő rendezésΘ(nlgn)Θ(nlgn)Θ(nlgn)
GyorsrendezésΘ(n2)Θ(nlgn)Θ(nlgn)

Oszd meg és uralkodj!

Mind az összefésülő rendezés, mind a gyorsrendezés ugyanazt a rekurzión alapuló paradigmát használja fel az algoritmus során. Ez a paradigma az oszd meg és uralkodj elv, ami azon alapul, hogy a megoldandó feladatot az eredetihez hasonló részfeladatokra bontja, megoldja azokat, majd a megoldott részfeladatokat összefésüli. Mivel az oszd-meg-és-uralkodj folyamat során a részfeladatokat rekurzívan oldja meg, az egyes részfeladatoknak az eredetinél mindig kisebbnek kell lenniük, és léteznie kell a részfeladatok alapesetének is. Az oszd-meg-és-uralkodj algoritmus három összetevőből áll:
  1. Oszd a feladatot részfeladatokra, amik ugyanannak a feladatnak kisebb változatai.
  2. Uralkodj a részfeladatok felett úgy, hogy rekurzívan megoldod azokat. Ha a részfeladat megfelelően kicsi, akkor oldd meg azt az alapeset szerint.
  3. Fésüld össze a részfeladatok megoldásait az eredeti probléma megoldásává.
Az oszd meg és uralkodj algoritmusok egyes lépéseit az alábbi tevékenységek sorozataként jegyezd meg: oszd fel részproblémákra, urald a részproblémákat, fésüld össze az eredményeket. Egy adott lépést a következőképpen szemléltethetünk, feltéve, hogy a felosztás során mindig két részfeladatot képezünk (vannak olyan oszd meg és uralkodj algoritmusok, melyek kettőnél több részfeladatot képeznek):
Ha egy vagy több rekurzív lépést kibontunk, akkor ezt kapjuk:
Mivel az oszd meg és uralkodj legalább két részfeladatot képez, ezért az több rekurzív hívást eredményez.
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.