5. cvičení

Témata hodiny

• Asymptotické meze
• Insertion sort

Průběh hodiny

Na cvičení 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).

Poté jsme si povídali o insertion sortu, jeho myšlence, pseudokódu a složitosti. Insertion sort jsme implementovali v C/Pythonu.

Poznámky

• Práce s poli v Pythonu. Pro formu: Ve skutečnosti jsou to seznamy, ale tím se netrapte.

Úkoly

1. Implementujte v C/Pythonu insertion sort.
2. Navrhněte algoritmus obracející pořadí prvku v poli. Spočítejte jeho přesnou časovou složitost T(n) a určete její asymptoticky těsný odhad Θ(g(n)). Implementujte jej v C/Pythonu.
3. Implementujte v C/Pythonu algoritmus počítající “násobilku” z jednoho z předchocích cvičení. Určete asymptotický dolní Ω(g(n)) a horní O(h(n)) odhad jeho časové složitosti.
4. Dořešte všechny asymptotické vztahy mezi základními funkcemi (konstantní, logaritmická, lineární, kvadratická, kubická, exponenciální, faktoriál).