@Dawav Po wymnożeniu masz f(n) = 6nlog(n) + 2n^2 + 1 Definicja "big O" nakłada górną "granicę" (barierę) na funkcję. Np. żeby f(n) była O(n^2) musi istnieć takie c (rzeczywiste), że dla każdej liczby większej niż jakieś x0 zachodzi cn^2 >= f(n). 3n^2 załatwi sprawę, więc f(n) jest O(N^2). Czy jest też O(n^3)? Oczywiście, tak samo jak i O(n^4), bo skoro istnieje funkcja kwadratowa która ogranicza f(n) z góry to każdy wyższy
@Chuczek: ok super, dziękuje pomogło ;) "małe o" nie będzie spełnione prawda? bo to jest od dołu a najmniejsza jaka jest możliwa dla "małe o" to o(n^2). Muszę pamietac o wymnazaniu tych nawiasów wszystkich , prosciej jest
@Dawav „Małe o” to granica od dołu? Nie znam niestety polskich oznaczeń i założyłem, że zrobiłeś pomyłkę w pytaniu. W angielskojęzycznej nomenklaturze dolna granica to „big Omega”. W takim wypadku jak najbardziej, f(n) nie jest o(n^3) (czy też Omega(n^3)) bo wielomian trzeciego stopnia rośnie szybciej niż f(n). I tak, w dziedzinie wielomianów największy możliwy ograniczający f(n) z dołu jest o(n^2).
@Chuczek: Tak omega nie jest. A little o jest spełnione do n^3 ? Według mnie tak , ponieważ cokolwiek podstawimy za c to i tak zawsze będzie spełnione? Jakby było little o od n^2 to by nie mogło być, ponieważ jakbyśmy dali 1*n^2 to nie byłaby spełniona zależność f(n)<=c*g(n). a cokolwiek podstawimy przed n^3 to będzie spełniona ta zależność. Dobrze rozumiem?
Muszę obliczyć złożoność obliczeniową danej funkcji
f(n)=2n(3log(n)+n)+1
i mam sprawdzić czy to jest spełnione
1. f(n) = O(n^2)
2. f(n) = o(n^3)
3. f(n) = Theta(nlog(n))
Z tego co się uczyłem to biorę sobie za f(n) =2n ponieważ reszta i tak nie gra roli przy takim wzorze.
i sprawdzam czy istnieje co najmniej jedno n, które spełnia zależność
dla 1.f(n)<=c*g(n)
dla 2. f(n)>=c*g(n)
i teraz dla 1 sobie podstawiam
g(n) =3n no i jest g(n) większa od f(n) a ze to jest szacowanie do góry to istnieje O(n^2)
dla 2 sobie podstawie za g(n) =1n więc jest spełnione ale to jest szacowanie do dołu wiec nie istnieje o(n^3)
tak samo theta nie istnieje bo muszą być dwa takie same złożoności dla takich samych n aby to było spełnione
dobrze rozumiem czy coś nie?
#algorytmy #programowanie
a Ty obliczasz zlozonosc obliczeniowa
Definicja "big O" nakłada górną "granicę" (barierę) na funkcję. Np. żeby f(n) była O(n^2) musi istnieć takie c (rzeczywiste), że dla każdej liczby większej niż jakieś x0 zachodzi cn^2 >= f(n). 3n^2 załatwi sprawę, więc f(n) jest O(N^2). Czy jest też O(n^3)? Oczywiście, tak samo jak i O(n^4), bo skoro istnieje funkcja kwadratowa która ogranicza f(n) z góry to każdy wyższy
Mój błąd był w małe o , małe o to