Rekurze, rekurence a quick sort

Upozornění na písemku a úkoly

Za dva týdny (27. a 28.11.) nás čeká písemka.
Ve středu 15.11. v 17:00 na webu cvičení zveřejním zadání zápočtového úkolu.

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

Implementujte quick sort v jazyce C.
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. Zkuste první sami, případně máte nápovědu níže.

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)).