→ Algorytmy004 → Rozpocznij Naukę / Ściągnij Fiszki MP3

Pytanie		Odpowiedź
Omikron(g(n)) = {f(n): istnieją dodatnie stałe c1, c2, n0, takie, że: rozpocznij naukę		0<=c1g(n)<=f(n)<=c2g(n) dla n>=n0}
dla Omikron, g(n) to rozpocznij naukę		asymptotycznie dokładne oszacowanie f(n)
f(n) E Omikron(g(n)) jest rozpocznij naukę		asymptotycznie nieujemna
dla Omikron, g(n) musi być rozpocznij naukę		asymptotycznie nieujemna
O(g(n)) = {f(n): istnieją dodatnie stałe c i n0, takie, że rozpocznij naukę		0 <= f(n) <= cg(n) dla wszystkich n>= n0}
graficzna ilustracja rozpocznij naukę		notacji Omikron
graficzna ilustracja rozpocznij naukę		notacji O
dla O(g(n)), g(n) to rozpocznij naukę		asymptotycznie górne ograniczenie f(n)
jeżeli f(n) = Omikron(g(n)) to rozpocznij naukę		f(n) = O(g(n))
Omikron(g(n)) zawiera się w rozpocznij naukę		O(g(n)) (jest podzbiorem)
funkcja kwadratowa ax^2 + bn + c, należy do rozpocznij naukę		Omikron(n^2) więc należy również do O(n^2)
Omega(g(n)) = {f(n): istnieją dodatnie stałe c i n0, takie, że rozpocznij naukę		0<= cg(n) <= f(n) dla wszystkich n>= n0
graficzna ilustracja rozpocznij naukę		notacji Omega
dla Omega: g(n) to rozpocznij naukę		asymptotycznie dolne ograniczenie f(n)
jeżeli f(n) = Omikron(g(n)) to rozpocznij naukę		f(n) = Omega(g(n))
czas działania algorytmu wynosi Omega(g(n)) rozpocznij naukę		dla kaŜdego dostatecznie duŜego n, jakiekolwiek dane wejściowe rozmiaru n weźmiemy, czas działania algorytmu na tych danych będzie nie mniejszy niŜ stała razy g(n)
Czas działania algorytmu sortowania przez wstawianie dla najlepszego przypadku wynosi rozpocznij naukę		Omega(n)
n=O(n^2) oznacza rozpocznij naukę		n E O(n^2)
2n^2 = 2n^2 + Omikron(n) możemy zapisać jako rozpocznij naukę		2n^2 = 2n^2 + f(n) gdzie f(n) E Omikron(n)
o(g(n))={f(n): dla każdej dodatniej stałej c>0 istnieje stała n0>0 taka, że rozpocznij naukę		0<=f(n)<cg(n) dla wszystkich n>= n0}
dla f(n)=O(g(n)) oszacowanie 0<= f(n) <= cg(n) zachodzi dla rozpocznij naukę		pewnej stałej c>0
dla f(n) = o(g(n)) oszacowanie 0<=f(n)<cg(n) zachodzi dla rozpocznij naukę		wszystkich stałych c>0
2n^2 ... o(n^2) rozpocznij naukę		!=
2n ... o(n^2) rozpocznij naukę		=
w(g(n)) = {f(n) dla każdej dodatniej stałej c > 0 istnieje stała n0 > 0 taka, że rozpocznij naukę		0<= cg(n)<f(n) dla n>= n0
n^2/2 ... w(n) rozpocznij naukę		=
n^2/2 ... w(n^2) rozpocznij naukę		!=

Algorytmy004

Musisz się zalogować, by móc napisać komentarz.