Какво трябва да знаем?
Асимптотични означения – O, o, Ω и Θ за безкрайно големи функции
Тези означения са въведени от Едмонд Ландау. Те намират приложения в анализа и анализа на алгоритми.
Функциите, които разглеждаме тук са с дефиниционна област положителните реални числа или положителните цели числа.
Предполагаме още, че те клонят към плюс безкрайност при клонене на аргумента също към плюс безкрайност.
Дефиниции
Нека f(x) и g(x) са две функции: R → R. Казваме, че f = O(g), когато съществуват реална, положителна константа c и
естествено число n0,
такива че за всяко n ≥ n0 е изпълнено f(n) ≤ cg(n).
Константата c трябва да е положителна.
Или, което е същото, че съществува околност на +∞, за която горното равенство е изпълнено.
f=O(g) се чете: „f е голямо O спрямо g” или „f асимптотично се доминира с точност до константа” от g.
Ясно е, че f = O(g) и g = O(f) тогава и само тогава, когато съществуват константи
c1 > 0 и c2 > 0, такива че за достатъчно големи n е изпълнено
c1g(n) ≤ f(n) ≤ c2g(n), което се означава с : f = Θ(g) (тета спрямо g).
Ако
то f = Θ(g).
Ако f = Θ(g) се казва, че двете функции имат “еднакво” асимптотично поведение.
Случаят в който константата е 1 се отбелязва с f ~ g.
Например полином от степен n асимптотично се доминира от xn .
В сила е още ln(1+x)=O(x).
Нека A е цяло число.
Броят на цифрите му n в B-ична бройна система се задава с формулата:
.
Релацията f=O(g) е транзитивна.
?
O(f)+O(g)=O(f+g)
?
Казва се , че f=o(g) в околност на +∞ ако
. o(f)+o(g)=o(f+g)
?
?
O(o(f))=o(O(f))=o(f) - малкото o поглъща голямото.
?
Много сложни оценки се решават по един прост начин – чрез неравенството:
,
където g(x) е растяща ( или по-общо ненамаляваща ) функция.
?
Ако използваме неравенството, лесно се показва, че
.
Какво ще научим?