5. cvičení

Témata hodiny

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ídáli o selection sortu, jeho myšlence, pseudokódu a složitosti. Selection sort jsme implementovali v C.

Úkoly

  1. Implementujte v C 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.
  3. Implementujte v C algoritmus počítající “násobilku” z minula. 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).