6. 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ídali o selection sortu, jeho myšlence, pseudokódu a složitosti. Selection sort jsme implementovali v jazyce C. Selection sort jsme nechali na příště.

Ú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 v nejhorším případě T(n) a určete její asymptoticky těsný odhad Θ(g(n)). Implementujte jej v jazyce C.
  3. Z minula snad máte navržený a implementovaný algoritmus vracející třetí největší prvek zadaného pole (velikosti n, obecně nemusí byt setříděné). Pokud algoritmus zatím nemáte, navrhněte jej. Poté určete jeho složitost v nejhorším případě (přesně i asymptoticky těsný odhad).
  4. Dořešte všechny asymptotické vztahy mezi základními funkcemi (konstantní, logaritmická, lineární, kvadratická, kubická, exponenciální, faktoriál).