Vybrané číselné funkce a rychlosti jejích růstu

Funkce absolutní hodnoty

• $f(n)=|n|$
• Růst je lineární ($O(n)$)

Funkce lineární

• $f(n)=n$
• $y=ax+b$
• Např. průchod spojovým seznamem

Kvadratická funkce

• $f(n)=n^2$
• Např. neefektivní třídící algoritmy (bubble sort)

Kubická funkce

• $f(n)=n^3$

Mocniná funkce se záporným exponentem

• $f(n)=n^{-1}$
• tzv. nepřímá úměrnost
• Rozdílné pokud je exponent sudý/lichý

Exponenciální funkce

• $f(n)=b^n$

1. $b>1$ - rostoucí
2. $b<1$ - klesající

• Růst zhruba $O(2^n)$ (v praxi téměr nepoužitelná)
• Např. SAT, obecně brute-force

Logaritmická funkce

• $f(n)=log(n)$
• Velmi dobře použitelný algoritmus v praxi
• Např. dělení problému na poloviny, binární hledání

Logaritmicko-lineární funkce

• $f(n)=n\cdot log(n)$
• Např. lepší třídící algoritmy (quick sort, merge sort)

Funkce faktoriál

• $f(n)=n!$
• Z hlediska O-notace nejhorší možnost rychlosti růstu
• Např. Počet možných permutací množiny, TSP

Funkce konstantní

• $f(n)=c$

Funkce sin, cos, tag, cotag

• $f(x)=sin(x)$
• $f(x)=cos(x)$
• $f(x)=tg(x)$
• $f(x)=cotg(x)$
•