Prezentacia - Vypoctova zlozitost algoritmov 19.10.2020 9:15

Zhrnutie prednášky

Prednáška sa venuje problému usporiadania postupnosti čísel (vnútorné triedenie v poli) z pohľadu výpočtovej zložitosti. Triediace algoritmy slúžia ako príklad toho, že jeden problém možno riešiť algoritmami s veľmi rôznou zložitosťou, a na nich sa demonštrujú algoritmické techniky zrýchľovania výpočtu. Veľkosť problému je označená N, čiže počet usporadúvaných čísel. Ako prvý je podrobne rozobraný bublinový variant, v ktorom sa porovnávajú a podľa potreby vymieňajú susedné prvky a maximum postupne prebubláva na koniec poľa. Následne je predstavený opačný variant s klesajúcim vnútorným cyklom, kde minimum prebubláva na začiatok. V oboch variantoch sa hranica vnútorného cyklu postupne zužuje, pretože už usporiadaná časť sa nekontroluje. Neskôr má nasledovať quick sort.

• - Správne ide o problém usporiadania, nie triedenia, a možno ho riešiť algoritmami s rôznou výpočtovou zložitosťou.
• - Veľkosť problému N je počet usporadúvaných čísel uložených v poli A.
• - Vnútorné triedenie prebieha v operačnej pamäti, vonkajšie pri veľkých súboroch na externom médiu.
• - Bublinové triedenie porovnáva a vymieňa susedné prvky, takže maximum postupne prebubláva na koniec.
• - Pre N prvkov stačí N-1 prechodov, lebo posledný zostávajúci prvok netreba usporadúvať.
• - Druhý variant ide odzadu a minimum prebubláva na začiatok, pričom sa dolná hranica cyklu zvyšuje.
• - Hranica vnútorného cyklu sa zužuje, lebo už usporiadanú časť poľa netreba znova porovnávať.

Zhrnutie pripravené s pomocou AI z prepisu videa.