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