Efektívne algoritmy a zložitosť - 06 - Rozdeľuj a panuj

Zhrnutie prednášky

Prednáška zopakuje triedenie MergeSort ako príklad metódy rozdeľuj a panuj. Algoritmus rekurzívne zotriedi ľavú a pravú polovicu poľa a potom ich zlúči funkciou Merge v lineárnom čase Θ(n), pričom využíva zarážky s hodnotou nekonečno. Analýza stromu rekurzie ukazuje, že každá úroveň stojí c·n práce a úrovní je približne 1 + log n, takže celková zložitosť je O(n log n). Metóda sa skladá z rozdelenia problému na podproblémy, ich rekurzívneho vyriešenia (malé sa riešia priamo) a kombinovania riešení. Ďalším príkladom je Quicksort, ktorý pri vyváženom výbere pivota beží v čase Θ(n log n), no pri zlom výbere až v Θ(n²). Na záver sa spomína úloha najväčšieho súvislého podpola, riešiteľná touto metódou.

• - MergeSort rozdelí pole na polovice, každú rekurzívne zotriedi a potom ich zlúči.
• - Zlúčenie dvoch utriedených polí (Merge) trvá Θ(n) a používa zarážky s hodnotou nekonečno.
• - Každá úroveň rekurzie stojí c·n práce a úrovní je približne 1 + log n, takže zložitosť je O(n log n).
• - Rozdeľuj a panuj: rozdeliť problém, vyriešiť podproblémy rekurzívne a skombinovať ich riešenia.
• - Quicksort pri dobrom výbere pivota beží v Θ(n log n), pri zlom v Θ(n²).
• - Verzia Quicksortu so zaručeným Θ(n log n) má príliš veľkú konštantu, a preto nie je praktická.
• - Úloha najväčšieho súvislého podpola sa dá riešiť metódou rozdeľuj a panuj.

Zhrnutie pripravené s pomocou AI z prepisu videa.