Rekurze, rekurence a quick sort

Témata

• Rekurze a rekurzivní algoritmy
• Rekurence a složitost rekurzivních algoritmů
• 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 aplikovat na návrhu a analýze rekurzivního algoritmu pro sčítání čísel v seznamu.

Řekli jsme si myšlenku třídění 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/Pythonu.
2. Navrhněte rekurzivní algoritmus pro výpoč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 platit Θ(T(n)) = Θ(T₁(n)) = Θ(T₂(n)).