share: true
aliases:
- Analýza rekurencí
Analýza rekurencí
Mějme rekurence (rekurzivní algoritmus) tvaru
- Motivace: popis složitosti rekurzivních algoritmů
- Řešení složitosti problému (operační, paměťová, …) velikosti
- rozdělíme na menších částí/problémů a vyřeším složitost na té menší instanci
- Těchto menších instancí máme celkově
- je nějaká další režie - typicky ono rozdělení na menší podproblémy a zkombinování zpět
Metody
Na jejich analýzu typicky využíváme následující metody
Značení
- Místo posloupností budeme dále používat funkce a , typicky s kladnými funkčními hodnotami a definované alespoň na , resp.
- Pokud velikost vstupu nemá velikost , musíme ještě řešit případné zaokrouhlení pomocí horní/dolní celé části
- Za počáteční podmínku považujeme
Vytvořeno: 28. 11. 2024, 22:29
Poslední aktualizace: 29. 11. 2024, 22:13