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.