Математическая логика и теория алгоритмов. Стенюшкина В.А. - 68 стр.

UptoLike

ВУЗ: 

ОГУ | Оренбург

Составители: 

Рубрика: 

(f(n)) равносильны. (Символ «О» читается как «О- большое», символ «Ω» - как
«Ω» - большое».) Асимптотические обозначения Θ, О, Ω могут использоваться
внутри формул. Например, если имеется запись Т(n) = 2Т(n/2) + Θ(n), то имеет-
ся в виду, что функция Θ(n) не меньше с
1
n и не больше с
2
n для некоторых конс-
тант с
1
, с
2
и достаточно больших n. А цепочка равенств типа 2n
2
+3n+1
=n
2
+Θ(n)=Θ(n
2
) понимается как последовательная асимптотическая оценка
функции.
Определение 4 Если f(n) = О(f(n)) и lim
n→∞
(f(n)/g(n))=0, то применяется
обозначение f(n)=о(g(n)) (« f от n есть о – малое от g от n»). При этом предпола-
гается, что f(n) и g(n) неотрицательны для достаточно больших n.
Определение 5 Если g (n)=o(f(n)), то говорят также, что f(n)= ω(g(n)) («f
от n есть ω - малое от g от n»). При этом уже предположено, что f(n) и g (n) не-
отрицательны для достаточно больших n.
Итак, запись f(n)=о(g(n)) означает, что для любого ε> 0 существует n
0
∈ N
такое, что 0 ≤ f(n) < εg(n) для всех n ≥ n
0
, а запись f(n)= ω(g(n)) означает, что для
любого с > 0 существует n
0
∈ N такое, что 0 ≤ сg(n) ≤ f(n) для всех n ≥ n
0.
Примеры
1
2n = о (n
2
), 2n
2
≠ о (n
2
)
2
n
2
/2=ω(n), n
2
/2 ≠ ω(n
2
)
Введенные характеристики асимптотического поведения функций обла-
дают некоторыми стандартными свойствами. Так, отношения Θ,O,Ω, о, ω тран-
зитивны, Θ, О, Ω рефлексивны, Θ симметрично. Пары отношений О и Ω, а так-
же о и ω взаимно обратимы.
3.4 Оценки роста стандартных функций
3.4.1 Полином от переменной n имеет вид р(n) = ∑
i=0
d
а
i
n
i
. Будем предпо-
лагать, что d – степень полинома. Тогда полином р(n)=О(n
d
). Говорят, что фун-
кция f(n) полиномиально ограничена, если f(n) = n
O(1)
, или f(n) = О(n
k
) для не-
которой константы k.
3.4.2 Экспонента от переменной n определяется как функция n → а
n
, а ≠
0. При а>1 экспонента растет быстрее любого полинома, то есть n
b
= o(a
n
). Для
вещественных х выполнено неравенство е
х
>1+х; если х≤1, то имеет место
оценка 1+х≤е
х
≤1+х+х
2
. Кроме того, можно отметить, что е
х
=1+х+Θ(х
2
), х→0.
Напомним, что е =2,71828…; е
х
= ∑
k=0
∞
х
k
/ k!.
3.4.3 Логарифмы – это функции n→log
b
n, b>0.Используются обозначе-
ния: log(n)=log
2
(n), ln(n)=log
e
(n). Напомним, что при х<1 выполняется равенс-
тво ln(1+х)=х-х
2
/2+х
3
/3-… . Для х>-1 справедливо: х/(1+ х)≤ln(1+х)≤х. Говорят,
что функция f(n) ограничена полилогарифмом, если f(n)=log
O(1)
n. Любой поли-
ном растет быстрее любого полилогарифма, то есть log
b
n=o (n
с
), с>0.
3.4.4 Факториалы – это функции n→n!= n(n–1)!, n=1, 2,… . Полагают
0!=1. Очевидно, n!≤n
n
. Более точно, n! = n
π
2 (n/е)
n
(1+Θ(1/n)), - формула Сти-
(f(n)) равносильны. (Символ «О» читается как «О- большое», символ «Ω» - как
«Ω» - большое».) Асимптотические обозначения Θ, О, Ω могут использоваться
внутри формул. Например, если имеется запись Т(n) = 2Т(n/2) + Θ(n), то имеет-
ся в виду, что функция Θ(n) не меньше с1n и не больше с2n для некоторых конс-
тант с1, с2 и достаточно больших n. А цепочка равенств типа 2n2+3n+1
=n2+Θ(n)=Θ(n2) понимается как последовательная асимптотическая оценка
функции.
       Определение 4 Если f(n) = О(f(n)) и lim n→∞(f(n)/g(n))=0, то применяется
обозначение f(n)=о(g(n)) (« f от n есть о – малое от g от n»). При этом предпола-
гается, что f(n) и g(n) неотрицательны для достаточно больших n.
       Определение 5 Если g (n)=o(f(n)), то говорят также, что f(n)= ω(g(n)) («f
от n есть ω - малое от g от n»). При этом уже предположено, что f(n) и g (n) не-
отрицательны для достаточно больших n.
       Итак, запись f(n)=о(g(n)) означает, что для любого ε> 0 существует n0 ∈ N
такое, что 0 ≤ f(n) < εg(n) для всех n ≥ n0, а запись f(n)= ω(g(n)) означает, что для
любого с > 0 существует n0 ∈ N такое, что 0 ≤ сg(n) ≤ f(n) для всех n ≥ n0.
       Примеры
       1     2n = о (n2), 2n2 ≠ о (n2)
       2     n2/2=ω(n), n2/2 ≠ ω(n2)
       Введенные характеристики асимптотического поведения функций обла-
дают некоторыми стандартными свойствами. Так, отношения Θ,O,Ω, о, ω тран-
зитивны, Θ, О, Ω рефлексивны, Θ симметрично. Пары отношений О и Ω, а так-
же о и ω взаимно обратимы.

       3.4 Оценки роста стандартных функций

      3.4.1 Полином от переменной n имеет вид р(n) = ∑i=0dаini. Будем предпо-
лагать, что d – степень полинома. Тогда полином р(n)=О(nd). Говорят, что фун-
кция f(n) полиномиально ограничена, если f(n) = n O(1), или f(n) = О(nk) для не-
которой константы k.
      3.4.2 Экспонента от переменной n определяется как функция n → а n, а ≠
0. При а>1 экспонента растет быстрее любого полинома, то есть nb = o(an). Для
вещественных х выполнено неравенство ех>1+х; если х≤1, то имеет место
оценка 1+х≤ех≤1+х+х2. Кроме того, можно отметить, что ех=1+х+Θ(х2), х→0.
Напомним, что е =2,71828…; ех = ∑k=0∞х k/ k!.
      3.4.3 Логарифмы – это функции n→logbn, b>0.Используются обозначе-
ния: log(n)=log2(n), ln(n)=loge(n). Напомним, что при х<1 выполняется равенс-
тво ln(1+х)=х-х2/2+х3/3-… . Для х>-1 справедливо: х/(1+ х)≤ln(1+х)≤х. Говорят,
что функция f(n) ограничена полилогарифмом, если f(n)=logO(1)n. Любой поли-
ном растет быстрее любого полилогарифма, то есть log bn=o (nс), с>0.
      3.4.4 Факториалы – это функции n→n!= n(n–1)!, n=1, 2,… . Полагают
0!=1. Очевидно, n!≤nn. Более точно, n! = 2πn (n/е)n(1+Θ(1/n)), - формула Сти-

Страницы