Cvicenie - Vypoctova zlozitost algoritmov 28.10.2020 11:00

Zhrnutie prednášky

Cvičenie z výpočtovej zložitosti algoritmov sa začalo samostatným autotestom o piatich úlohách, ktorý zhŕňal predchádzajúce hodiny: určovanie časovej zložitosti, asymptotických hraníc a prevod rekurentných vzťahov na nerekurzívne. Následne sa spoločne riešili úlohy. V prvej sa počítal počet priradení v algoritme s tromi za sebou idúcimi for cyklami, kde zložitosť závisí od dvoch parametrov N a K a vyjadruje sa pomocou súm, pričom počet opakovaní cyklu je horná hranica mínus dolná plus 1. V druhej úlohe sa z rekurentného vzťahu T(n) = T(n−1) + n − 1 s T(1) = 0 počítalo T(10) = 45, najprv postupným dosadzovaním a potom sa začalo odvádzať nerekurzívne vyjadrenie rozpisovaním rekurencie.

• - Časová zložitosť môže závisieť od viacerých vstupných parametrov, napr. T(N, K).
• - Zložitosť for cyklu sa vyjadruje ako súčet zložitostí jeho tela; postupnosť cyklov sa sčítava, vnorené cykly dávajú vnorené sumy.
• - Počet opakovaní cyklu od dolnej po hornú hranicu je horná − dolná + 1.
• - Ak telo cyklu nezávisí od riadiacej premennej, stačí ho vynásobiť počtom opakovaní.
• - Rekurentný vzťah T(n) = T(n−1) + n − 1 s T(1) = 0 dáva T(10) = 45.
• - Hodnotu rekurencie možno počítať postupne od T(1), no pre veľké n je výhodnejšie nerekurzívne vyjadrenie získané opakovaným dosadzovaním.
• - Zvyšné úlohy autotestu zahŕňali asymptotickú dolnú hranicu s konštantami C a M, usporiadanie funkcií zložitosti podľa rýchlosti a tvrdenia o pojmoch zložitosti.

Zhrnutie pripravené s pomocou AI z prepisu videa.