navigation
hledat
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
|
courses:a4m01tal:zkouska-2014-06-12 [2014/06/17 21:13] suchyon6 [Různá teorie] |
courses:a4m01tal:zkouska-2014-06-12 [2025/01/03 18:28] (aktuální) |
||
|---|---|---|---|
| Řádek 7: | Řádek 7: | ||
| Omega je omezeni zespoda f(n) >= c * g(n), tzn hledame nejvetsi (a nejjednodussi) takovou fci, ktera splnuje tuto rovnost | Omega je omezeni zespoda f(n) >= c * g(n), tzn hledame nejvetsi (a nejjednodussi) takovou fci, ktera splnuje tuto rovnost | ||
| f(n) = n^2.lg(n) + suma i=0..n (i^2) // sumu si vzorcem na soucet prevedeme | f(n) = n^2.lg(n) + suma i=0..n (i^2) // sumu si vzorcem na soucet prevedeme | ||
| - | f(n) = n^2.lg(n) + n*(1+n^2)/2 // coz da O(n^3) | + | f(n) = n^2.lg(n) + n*(1+n^2)/2 // coz da O(n^3), !!! maple říká (1/3)*n^3+(1/2)*n^2+(1/6)*n |
| f(n) = n^2.lg(n) + n/2 + n^3/2 // n^3 > n^2.lg(n), takze nas zajima jen n^3 | f(n) = n^2.lg(n) + n/2 + n^3/2 // n^3 > n^2.lg(n), takze nas zajima jen n^3 | ||
| --> g(n) = O(n^3) | --> g(n) = O(n^3) | ||
