Lekce 5 - Dynamické programování
V minulé lekci, Časová složitost algoritmů a jejich odhad složitosti, jsme se blíže podívali na časovou složitost algoritmů. Naučili jsme se odhadnout jejich složitost.
V dnešním tutoriálu o teorii algoritmů si představíme dynamické programování, které využívá již dříve spočítané výsledky. Jedná se o počítání výsledků, kdy mezivýsledky vznikají průběžně.
Dynamické programování si ukážeme nejen praktickém příkladu výpočtu Fibonacciho čísla, ale zmíníme si i jeho další využití.
Výpočet Fibonacciho čísla v dynamickém programování
Nejznámějším příkladem pro dynamické programování je výpočet n-tého Fibonacciho čísla.
Výpočet si ukážeme dvěma způsoby, a to pomocí:
- rekurentního výpočtu,
- uložení výsledků do pole,
- uložení výsledků do třech proměnných.
Rekurentní výpočet
Matematický rekurentní vzorec vypadá takto:
fib(0) = 1, fib(1) = 1 a
fib(n) = fib(n-1) + fib(n-2). Číselná řada začíná touto
sekvencí čísel: 1, 1, 2,
3, 5, 8, 13,
21, 34, 55. Tento rekurentní vzorec je
správně, ale je velmi neefektivní. Vyžaduje totiž mnoho opakování
výpočtu stejných hodnot, což vede k mnoha zbytečným a opakovaným
výpočtům.
Z obrázku níže je zřejmé, že například fib(2) se
počítá úplně zbytečně několikrát:
...konec náhledu článku...
Pokračuj dál
Došel jsi až sem a to je super! Věříme, že ti první lekce ukázaly něco nového a užitečného.
Chceš v kurzu pokračovat? Přejdi do prémiové sekce.
Koupit tento kurz
Obsah článku spadá pod licenci Premium, koupí článku souhlasíš se smluvními podmínkami.
- Neomezený a trvalý přístup k jednotlivým lekcím.
- Kvalitní znalosti v oblasti IT.
- Dovednosti, které ti pomohou získat vysněnou a dobře placenou práci.
Popis článku
Požadovaný článek má následující obsah:
V tutoriálu o teorii algoritmů si představíme dynamické programování, které využívá již dříve spočítané výsledky.
Kredity získáš, když podpoříš naši síť. To můžeš udělat buď zasláním symbolické částky na podporu provozu nebo přidáním obsahu na síť.
