Rekurze: Porovnání verzí
Smazaný obsah Přidaný obsah
→Fibonacciho posloupnost: stovnani s tabelaci |
→Tabelace: ++ |
||
Řádek 253:
[[Tabelace]] je způsob odstraňování neefektivity pocházející z opakovaných volání se stejnými argumenty. Spočítané výsledky se ukládají (např. do [[Pole (datová struktura)|pole]]) a místo opakovaného volání se použije výsledek z tabulky, do které se zaznamená po prvním výpočtu s danými argumenty. Položky tabulky potřebují kromě uložené hodnoty 1 bit navíc, který určuje, zda jsou data platná, tj. už spočítána. Tabelace se často používá v [[dynamické programování|dynamickém programování]]. Tento přístup je [[trade-off]] času a paměti.
Pole může být vícerozměrné, kdy počet rozměrů odpovídá počtu argumentů. Anebo jednorozměrné, použité jako hašovací tabulka. První reprezentace je výhodná, pokud jsou počítané hodnoty husté, druhá je spíše pro řídké.
Výhoda je, že nemusíme měnit rekurzivní algoritmus. Nevýhoda je potřeba paměti pro tabulku, která je případně větší než při "ručním" návrhu a počítání zdola. V případě Fibonacciho čísel přímočaře použijeme pole P[] velikosti N, kdežto při ručním návrhu stačí pamatovat si poslední dvě čísla.▼
▲Výhoda tabelace je, že nemusíme měnit rekurzivní algoritmus. Nevýhoda je potřeba paměti pro tabulku, která je případně větší než při "ručním" návrhu a počítání zdola. V případě Fibonacciho čísel přímočaře použijeme pole P[] velikosti N, kdežto při ručním návrhu stačí pamatovat si poslední dvě čísla.
Speciálně, některé úlohy dynamického programování dovolují reformulaci algoritmu šetřící paměť.
<!--Pokud je struktura výpočtu pravidelná, resp. známá anebo odvoditelná, tak je efektivnější výpočet zdola, tj. bez rekurze, když už máme pole -->
Tabelace nemá smysl, pokud se počítají v rekurzi různé hodnoty,
=== Odstraňování rekurze ===
| |||