|
question |
réponse |
Omikron(g(n)) = {f(n): istnieją dodatnie stałe c1, c2, n0, takie, że: commencer à apprendre
|
|
0<=c1g(n)<=f(n)<=c2g(n) dla n>=n0}
|
|
|
|
commencer à apprendre
|
|
asymptotycznie dokładne oszacowanie f(n)
|
|
|
f(n) E Omikron(g(n)) jest commencer à apprendre
|
|
|
|
|
dla Omikron, g(n) musi być commencer à apprendre
|
|
|
|
|
O(g(n)) = {f(n): istnieją dodatnie stałe c i n0, takie, że commencer à apprendre
|
|
0 <= f(n) <= cg(n) dla wszystkich n>= n0}
|
|
|
|
commencer à apprendre
|
|
|
|
|
|
commencer à apprendre
|
|
|
|
|
|
commencer à apprendre
|
|
asymptotycznie górne ograniczenie f(n)
|
|
|
jeżeli f(n) = Omikron(g(n)) to commencer à apprendre
|
|
|
|
|
Omikron(g(n)) zawiera się w commencer à apprendre
|
|
O(g(n)) (jest podzbiorem)
|
|
|
funkcja kwadratowa ax^2 + bn + c, należy do commencer à apprendre
|
|
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 commencer à apprendre
|
|
0<= cg(n) <= f(n) dla wszystkich n>= n0
|
|
|
|
commencer à apprendre
|
|
|
|
|
|
commencer à apprendre
|
|
asymptotycznie dolne ograniczenie f(n)
|
|
|
jeżeli f(n) = Omikron(g(n)) to commencer à apprendre
|
|
|
|
|
czas działania algorytmu wynosi Omega(g(n)) commencer à apprendre
|
|
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 commencer à apprendre
|
|
|
|
|
|
commencer à apprendre
|
|
|
|
|
2n^2 = 2n^2 + Omikron(n) możemy zapisać jako commencer à apprendre
|
|
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 commencer à apprendre
|
|
0<=f(n)<cg(n) dla wszystkich n>= n0}
|
|
|
dla f(n)=O(g(n)) oszacowanie 0<= f(n) <= cg(n) zachodzi dla commencer à apprendre
|
|
|
|
|
dla f(n) = o(g(n)) oszacowanie 0<=f(n)<cg(n) zachodzi dla commencer à apprendre
|
|
|
|
|
|
commencer à apprendre
|
|
|
|
|
|
commencer à apprendre
|
|
|
|
|
w(g(n)) = {f(n) dla każdej dodatniej stałej c > 0 istnieje stała n0 > 0 taka, że commencer à apprendre
|
|
0<= cg(n)<f(n) dla n>= n0
|
|
|
|
commencer à apprendre
|
|
|
|
|
|
commencer à apprendre
|
|
|
|
|
