Merge sort a asymptotická složitost

Témata cvičení

• merge sort
• asymptotická složitost

Průběh hodiny

Nejprve jsme prošli řešení prvního úkolu. Dále jsme se podívali na algoritmus merge sort a zkusili si jej simulovat na poli čísel. Nakonec jsme prošli definice horních, dolních a těsných asymptotických mezí a jejich význam. Podívali jsme se na několik příkladů, zejména na vztahy mezi vybranými funkcemi z předchozích cvičení (konstantní, logaritmická, lineární, kvadratická, kubická, exponenciální, faktoriál).

Domácí úkol 2

• Třetí zápočtový domácí úkol najdete zde.
• Termín odevzdání je začátek příštího cvičení.
• Pokud na cvičení nemůžete přijít, pošlete úkol do začátku cvičení mailem.

Úkoly k procvičení

1. dořešte příklad ověřující hierarchii tříd funkcí ze cvičení, tj. dokažte všechny vztahy.