Szakkörök‎ > ‎Algoritmus szakkör‎ > ‎2013-2014‎ > ‎

8. alkalom

A mohó algoritmusok úgy oldanak meg optimalizációs problémákat, hogy mindig a lokálisan legjobbnak tűnő választás szerint haladnak tovább a megoldás felépítésével. Ez néha célravezető, néha nem. ( http://en.wikipedia.org/wiki/Greedy_algorithm , http://hu.wikipedia.org/wiki/Matroid )

A "lokálisan legjobb" lépés kiválasztása gyakran elemek valamilyen rendezés szerint bejárásán alapul. Ezért a mohó algoritmusok vizsgálata előtt célszerű átismételni a legfontosabb rendezési algoritmusokat. Tipikusan két hatékonysági osztály fordul elő. Például az egyszerű cserés rendezés O(N2), a gyorsrendezés O(N log N) "bonyolultságú". A gyorsabb rendezésre akkor van szükség, ha a rendezendő elemek száma meghaladja 104 = 10000-et.

Feladatok