4. cvičení

Témata hodiny

• Asymptotické meze
• Selection 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 selection sortu, jeho myšlence, pseudokódu a složitosti. Selection 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 selection 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 předminule. Určete asymptotický dolní Ω(g(n)) a horní O(h(n)) odhad jeho časové složitosti.
4. Navrhněte a implementujte v C algoritmus vracející třetí největší prvek zadaného pole (velikosti n, obecně nemusí byt setříděné). Určete jeho složitost (přesně i asymptoticky těsný odhad).
5. Dořešte všechny asymptotické vztahy mezi základními funkcemi (konstantní, logaritmická, lineární, kvadratická, kubická, exponenciální, faktoriál).