Složitost, implementace algoritmu
Témata hodiny
- Složitost v nejhorším a v průměrném případě
- Implementace jednoduchéno algoritmu
Průběh hodiny
- Prošli jsme si pojmy z přednášky týkající se složitosti algoritmů.
- Podívali jsme se na problém s četností písmen ve slově z minula.
- Podívali jsme se na problém násobení pomocí sčítání (na doma z minula).
- Ukázali jsme si tři algoritmy, které jej řeší.
- Zmínili jsme rekurzi. Jedno z řeešení bylo rekurzivní.
- Rešili jsme, co je velikost vstupu.
- Bavili jsme se o jejich složitosti (nerekurzivní verze) v nejhorším i průměrném případě.
Úkoly k procvičení
- Implementujte v jazyce C algoritmus pro sčítání dvou přirozených čísel, jak jej znáte ze ZŠ.
- Implementujte v jazyce C algoritmy navržené minule. Rešte jen ty, ke kterým znáte potřebné konstrukce v jazyce C.