Cvicenie - Vypoctova zlozitost algoritmov 11.11.2020 13:00

Zhrnutie prednášky

Cvičenie najprv zopakovalo triediace algoritmy: pomalé s časovou zložitosťou O(n²) (Bubble Sort, Shaker Sort, triedenie výberom) a rýchle s O(n log n) (Merge Sort, Heap Sort a Quicksort, ktorý je v najhoršom prípade O(n²), no v priemernom prípade patrí medzi najrýchlejšie). Následne sa pozornosť presunula na metódu rozdeľuj a panuj a jej nevhodné použitie, keď sa podproblémy neriešia nezávisle a výpočty sa opakujú; riešením je dynamické programovanie. Študenti v Jave implementovali rekurzívny výpočet kombinačného čísla N nad K podľa vzťahu C(n,k) = C(n-1,k) + C(n-1,k-1) s počítadlom sčítaní. Experimentálne sa ukázalo, že počet sčítaní je výsledok mínus 1, pretože výsledok sa skladá po jednotkách z triviálnych prípadov, a preto zložitosť veľmi rýchlo rastie. Na záver sa zložitosť vyjadrila rekurentným vzťahom T(n,k) = T(n-1,k) + T(n-1,k-1) + 1.

• - Pomalé triedenia (Bubble Sort, Shaker Sort, triedenie výberom) majú zložitosť O(n²), rýchle (Merge Sort, Heap Sort, Quicksort) O(n log n).
• - Quicksort je v najhoršom prípade O(n²), v priemernom O(n log n) a v praxi patrí medzi najrýchlejšie.
• - Rozdeľuj a panuj zrýchľuje algoritmy len pri nezávislých podproblémoch; pri závislých sa výpočty opakujú.
• - Riešením opakujúcich sa výpočtov je dynamické programovanie.
• - Kombinačné číslo N nad K udáva počet k-prvkových podmnožín n-prvkovej množiny a počíta sa rekurzívne podľa Pascalovho trojuholníka.
• - Počet sčítaní v rekurzívnom výpočte je rovný výsledku mínus 1, takže zložitosť rastie exponenciálne a pre veľké vstupy pretečie aj typ long.
• - Zložitosť rekurzívneho algoritmu sa vyjadruje rekurentným vzťahom T(n,k) = T(n-1,k) + T(n-1,k-1) + 1 s triviálnymi prípadmi rovnými 0.

Zhrnutie pripravené s pomocou AI z prepisu videa.