Rekurze, rekurence a quick sort

Průběh cvičení

Nejprve jsme si řekli něco o rekurzivních algoritmech a o rekurzi jako takové. Ukázali jsme si jednoduchý rekurzivní algoritmus pro spočítání délky spojového seznamu. Určili jsme jeho složitost Θ(n) vyřešením rekurence T(n) = Θ(1) + T(n−1). Myšlenku jste si pak sami zkusili apikovat na návrhu a analýze rekurzivního algoritmu pro sčítání čísel v seznamu.

Řekli jsme si myšlenku třízení quick sortem a ukázali si a okomentovali pseudokódy. Stručně jsme probrali složitost v nejhorším i v průměrném případě.

Úkoly

1. Implementujte quick sort v jazyce C/Python.
2. Navrhněte rekurzivní algoritmus pro výpčet n-tého Fibonacciho čísla a určete jeho složitost - vyjádřete ji rekurencí a tu pak vyřešte. (Nápověda: jednodušší, než dělat to přímo, je ohraničit danou rekurenci T(n) nějakou T′(n) v jednodušší podobě shora a jinou T″(n) v jednodušší podobě zespoda. Pokud se to povede tak, že Θ(T′(n)) = Θ(T″(n)), tak díky T″(n) ≤ T(n) ≤ T′(n) bude paltit Θ(T(n)) = Θ(T′(n)) = Θ(T″(n)).