UKTG Predednáška 13

Zhrnutie prednášky

Prednáška formalizuje asymptotické odhady funkcií, ktoré sa neformálne používajú pri analýze časovej zložitosti programov, napríklad pri triedení vkladaním, kde počet príkazov n²−n+3 zjednodušene považujeme za rádovo n². Takéto odhady sú užitočné aj v kombinatorike, napríklad pri faktoriáli alebo sumách, ktoré nevieme presne vyčísliť. Zavádza sa definícia: funkcia f rastie najviac tak rýchlo ako g, ak existuje kladná konštanta c a prirodzené n₀ také, že |f(n)| ≤ c·g(n) pre všetky n > n₀, čo sa zapisuje f(n) = O(g(n)). Definícia je ilustrovaná príkladmi n² = O(n³), 4n² = O(n³) a 4n² = O(n²).

• - Asymptotické odhady zjednodušujú zložité funkcie, napr. n²−n+3 na rádovo n².
• - Pri analýze algoritmov, napríklad triedenia vkladaním, nezáleží na konštantách ani členoch nižšieho rádu.
• - Odhady pomáhajú aj v kombinatorike pri faktoriáli a nepočítateľných sumách.
• - Nerovnosť f ≤ g stačí požadovať až od nejakého n₀, nie pre všetky n.
• - Vynásobenie funkcie g kladnou konštantou c umožňuje ignorovať konštanty.
• - Definícia f(n) = O(g(n)): existuje c > 0 a n₀ tak, že |f(n)| ≤ c·g(n) pre všetky n > n₀.
• - Príklady: n² = O(n³), 4n² = O(n³) od n ≥ 4 a 4n² = O(n²) s konštantou 4.

Zhrnutie pripravené s pomocou AI z prepisu videa.