Haskell Hero

Příklad

Určete, která z následujících funkcí rychleji počítá umocňování na přirozený exponent.

umocni1 _ 0  =  1
umocni1 x n  =  x * umocni x (n-1)

umocni2 _ 0  =  1
umocni2 x n  =  if even n then r else x * r
                where r = umocni2 (x * x) (n ‘div‘ 2)

Zkusme si pro představu vyhodnotit výrazy umocni1 5 1 a umocni2 5 1.

umocni1 5 1

~>  5 * umocni1 5 (1-1)
~>  5 * umocni1 5 0
~>  5 * 1
~>  5

umocni2 5 1

~>  if even 1 then r else 5 * r
    where r = umocni2 (5 * 5) (1 ‘div‘ 2)
~>  if False  then r else 5 * r
    where r = umocni2 (5 * 5) (1 ‘div‘ 2)
~>  5 * umocni2 (5 * 5) (1 ‘div‘ 2)
~>  5 * umocni2 (5 * 5) 0
~>  5 * 1
~>  5

umocni1 5 10

~>2   5 * umocni 5 9
~>2   5 * 5 * umocni 5 8
~>2   5 * 5 * 5 * umocni 5 7
~>14  5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * umocni 5 0
~>    5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 1
~>10  9765625

umocni2 5 10

~>3   umocni2 (5 * 5) (10 ‘div‘ 2)
~>    umocni2 (5 * 5) 5
~>3   5 * 5 * umocni2 (5 * 5 * 5 * 5) (5 ‘div‘ 2)
~>    5 * 5 * umocni2 (5 * 5 * 5 * 5) 2
~>3   5 * 5 * umocni2 (5 * 5 * 5 * 5 * 5 * 5 * 5 * 5) (2 ‘div‘ 2)
~>    5 * 5 * umocni2 (5 * 5 * 5 * 5 * 5 * 5 * 5 * 5) 1
~>3   5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 
        umocni2 (5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 *
                 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5) (1 ‘div‘ 2)
~>    5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 
        umocni2 (5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 *
                 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5) 0
~>4   5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 1
~>10  9765625

Časová složitost zkoumá náročnost výpočtu v závislosti na velikosti argumentů. Nyní si povíme základní věci z této problematiky.

Funkce, jejichž výpočet trvá vždy konstantní počet kroků, mají konstantní časovou složitost.

Příkladem může být funkce head v závislosti na délce seznamu v argumentu.

head [1]      ~>  1
head [1,2,3]  ~>  1
head [1,2,3,4,5,6,7,8,9,10]  ~>  1

Funkce, jejichž doba vyhodnocení lineárně stoupá s velikostí argumentů, mají lineární časovou složitost.

Například funkce map (+1) má lineární složitost vzhledem k délce seznamu v argumentu.

map (+1) [1]

~> 1+1 : map (+1) []
~> 1+1 : []
~>  2  : []

map (+1) [1,2]

~> 1+1 : map (+1) [2]
~> 1+1 : 2+1 : map (+1) []
~> 1+1 : 2+1 : []
~>  2  : 2+1 : []
~>  2  :  3  : []

map (+1) [1,2,3]

~> 1+1 : map (+1) [2,3]
~> 1+1 : 2+1 : map (+1) [3]
~> 1+1 : 2+1 : 3+1 : map (+1) []
~> 1+1 : 2+1 : 3+1 : []
~>  2  : 2+1 : 3+1 : []
~>  2  :  3  : 3+1 : []
~>  2  :  3  :  4  : []

Obecně tedy můžeme říct, že s každým dalším prvkem v seznamu vzroste časová složitost o konstantní počet kroků, v našem případě o dva. V takovém případě má funkce lineární časovou složitost.

Mějme funkci jeDvakrat :: Eq a => [a] -> Bool, kde se výraz jeDvakrat s vyhodnotí na True, pokud jsou v seznamu s dva stejné prvky, a na False, pokud je tam každý prvek pouze jednou.

Místo přesné definice si pouze řekněme, jak bude taková funkce pracovat.

• pro první prvek seznamu s zkontroluj, zda se nevyskytuje ještě někde dále v seznamu s
• pokud narazíš na takový výskyt, vyhodnoť se na True
• pokud se dále nevyskytuje, zavolej rekurzivně funkci jeDvakrat na seznam s bez prvního prvku

Předpokládejme, že porovnání dvou prvků trvá konstantní počet kroků. S každým prvkem seznamu se projdou ostatní prvky seznamu. Čili se n-krát provede n kroků, kde n je délka seznamu s. Což nám dává složitost n*n, neboli n^2. Budeme říkat, že funkce, jejíž vyhodnocení trvá n^2 kroků, má kvadratickou časovou složitost.

Dále ještě existují funkce, jejichž vyhodnocení trvá n^3 kroků. Takové funkce mají kubickou časovou složitost. Obecně o funkcích se složitostí n^a, kde a je konstanta, říkáme, že mají polynomiální časovou složitost.

Existují i funkce, které pracují déle než konstantně, ale kratčeji než lineárně. A to jsou funkce s logaritmickou časovou složitostí.

Příkladem takové funkce může být například následující funkce:

pocitej x  =  if x < 1 then 0
                       else pocitej (x `div` 2)

    pocitej 5
~>  pocitej 2
~>  pocitej 1
~>  pocitej 0
~>  0

    pocitej 10
~>  pocitej 5
~>  pocitej 2
~>  pocitej 1
~>  pocitej 0
~>  0

    pocitej 1000
~>  pocitej 500
~>  pocitej 250
~>  pocitej 125
~>  pocitej 62
~>  pocitej 31
~>  pocitej 15
~>  pocitej 7
~>  pocitej 3
~>  pocitej 1
~>  pocitej 0
~>  0