Witam,
Moglbys ktos sprawdzic czy dobrze to rozwiazalem i pomoc w nierozwiazanych przykladach?
f1(n) = 0.01n + logn^10 = O(n)
f2(n) = 2^(log podstawa 4 *n) = tutaj nie wiem jak rozwiązać tzn.
znalazłem wzór taki, ale nie wiem jak go tutaj wykorzystac: log podstawa b * x = y ; b^y = x
f3(n) = log podstawa 2 * 2^(n^2) = O(n^2)
f4(n) = n^0.5 + log n = O(n^0.5)
0
1
- A działania na logarytmach były w szkole? o_O Zmień podstawę logarytmu na 2 a potem zauważ że
2^log2(x) = xz definicji. - O ile ta gwiazdka oznacza u ciebie w rzeczywistości Z CZEGO LICZYSZ LOGARYTM to tak. Ale takiego oznaczenia się nigdy nie stosuje...
0
@Shalom
Dzięki
Ale teraz zastanawia mnie jeszcze jedna rzecz, bo otrzymuje następujące wyniki:
f1 = O(n)
f2 = Θ(n)
f3 = O(n^(1/2))
f4 = Θ(n^2)
i teraz chciałbym to ułożyć od najmniejszej złożoności do największej to czy będzie tak poprawnie:
f3 < f1 < f2 < f4
Chodzi o to czy O - czyli "co najwyżej" ma mniejszą złożoność od Θ - "jest dokładnie", raczej tak jest, ale wole się upewnić.
1
Generalnie tak, chociaż ja bym powiedział że prędzej f1 <= f2 bo O(n) może równie dobrze być faktycznie theta(n)