ADŠ prednáška 03: O-notácia a asymptotické odhady časovej zložitosti

Zhrnutie prednášky

Prednáška nadväzuje na predchádzajúcu tému časovej zložitosti algoritmov a zavádza formálnu notáciu na jej zápis. Časová zložitosť v najhoršom prípade je funkcia, ktorá veľkosti vstupu priraďuje maximálny počet elementárnych krokov algoritmu na všetkých vstupoch danej veľkosti. Konštantné faktory (napr. rýchlosť hardvéru) ani menej významné členy nie sú pri odhadoch podstatné, preto ich možno zanedbať. Na zápis horného asymptotického odhadu sa preberá z matematickej analýzy veľké O: trieda O(g) obsahuje funkcie f, pre ktoré existuje kladná konštanta c a hranica n0 tak, že pre všetky n ≥ n0 platí f(n) ≤ c·g(n). Definícia je ilustrovaná na grafoch, napríklad 3n² plus drobné členy je O(n²) a kvadratická funkcia je asymptoticky predbehnutá kubickou.

• - Časová zložitosť v najhoršom prípade je funkcia veľkosti vstupu vracajúca maximum počtu krokov na všetkých vstupoch danej veľkosti.
• - Počítajú sa abstraktné elementárne kroky, nie reálny čas na konkrétnom hardvéri či procesore.
• - Konštantné násobky a menej významné členy (napr. 13n popri n²) sa pri asymptotickej analýze zanedbávajú.
• - Veľké O je operátor, ktorý z funkcie g vytvorí triedu funkcií rastúcich najviac tak rýchlo ako g.
• - Formálna definícia: f ∈ O(g), ak existujú c > 0 a n0 také, že pre všetky n ≥ n0 platí f(n) ≤ c·g(n).
• - Na malých vstupoch sa funkcie môžu správať ľubovoľne, rozhoduje len správanie od hranice n0 ďalej.
• - Príklad: 3n² + drobné členy je O(n²), keďže 4n² ju od nejakého miesta prevyšuje.

Zhrnutie pripravené s pomocou AI z prepisu videa.