Параллель эта, впрочем, весьма условна: свойства числовых неравенств не переносятся на функции. Например, для любых двух чисел а и Ь всегда или а Ь, или а Ь, однако нельзя утверждать, что для любых двух (положительных) функций /(га) и д(п) или /(га) = 0(д(п)), или /(га) = Q(g(n)). В самом деле, можно проверить, что ни одно из этих двух соотношений не выполнено для /(га) = га и д(п) = n1+smn (показатель степени в выражении для д(п) меняется в интервале от 0 до 2). Заметим ещё, что для чисел а Ь влечёт а < Ь или а = Ь, в то время как для функций /(га) = 0(д(п)) не влечёт /(га) = о(д(п)) или /(га) = Q(g(n)).

Упражнения

2.1-1 Пусть /(га) и д(п) неотрицательны для достаточно больших га. Покажите, что max(/(ra),#(га)) = в(/(га) + д(п)).

2.1-2 Покажите, что

(п + а)ь = в{пь)(2.2)

для любого вещественного а и для любого Ь > 0.

2.1-3 Почему утверждение «время работы алгоритма А не меньше О (га2)» не имеет смысла?

2.1-4 Можно ли утверждать, что 2п+1 = 0(2П)? Что 22п = 0(2П)? 2.1-5 Докажите теорему 2.1.

2.1-6 Приведите пример функций /(га) и д(га), для которых /(га) = 0(д(п)), но /(га) ф о(д(п)) и /(га) ф в(д(п)).

2.1-7 Покажите, что свойства /(га) = о(д(п)) и /(га) = uj(g(n)) не могут быть выполнены одновременно.

2.1-8 Асимптотические обозначения могут быть введены и для функций, зависящих от нескольких параметров. Говорят, что /(то, га) = 0(д(т, га)), если найдутся гао, тоо и положительное с, для которых 0 /(то, га) сд(т,п) для всех га гао и то тоо- Дайте аналогичные определения для Q(g(m, га)) и £}(д(т, га)).

2.2. Стандартные функции и обозначения Монотонность

Говорят, что функция /(га) монотонно возрастает (is monoton-ically increasing), если /(то) f(n) при то га. Говорят, что

функция /(га) монотонно убывает (is monotonically decreasing), если /(то) f(n) при то га. Говорят, что функция /(га) строго возрастает (is strictly increasing), если /(то) < /(га) при то < га. Говорят, что функция /(га) строго убывает (is strictly decreasing), если /(то) > /(га) при то < га.

Целые приближения снизу и сверху

Для любого вещественного числа ж через [х\ (the floor of ж) мы обозначаем его целую часть, т.е. наибольшее целое число, не превосходящее х. Симметричным образом [~ж] (the ceiling of ж) обозначает наименьшее целое число, не меньшее ж. Очевидно,

ж - 1 < [ж] ж [ж] < ж + 1

для любого ж. Кроме того,

[га/2] + [п/2\ = га

для любого целого га. Наконец, для любого ж и для любых целых положительных а и Ь имеем

\\х/а]/Ъ] = \х/аЪ](2.3)

и

[[х/а\/Ъ\ = [х/аЪ\(2.4)

(чтобы убедиться в этом, полезно заметить, что для любого z и для целого га свойства га z и га [z\ равносильны). Функции ж н-> [х\ и ж н-т- [ж] монотонно возрастают.

Многочлены

Многочленом (полиномом) степени d от переменной га (polynomial in га of degree d) называют функцию

d

р{п) = 2 агпг

8 = 0

(d - неотрицательное целое число). Числа ао, osi,..., a,i называют коэффициентами (coefficients) многочлена. Мы считаем, что старший коэффициент a,i не равен нулю (если это не так, уменьшим d - это можно сделать, если только многочлен не равен нулю тождественно).

Для больших значений га знак многочлена р(п) определяется старшим коэффициентом (остальные члены малы по сравнению с

ним), так что при a,i > 0 многочлен р(п) асимптотически положителен (положителен при больших га) и можно написать р(п) = e(nd).

При а 0 функция га \-> па монотонно возрастает, при а О - монотонно убывает. Говорят, что функция /(га) полиномиально ограничена, если /(га) = ra°W, или, другими словами, если /(га) = 0{пк) для некоторой константы к (см. упр. 2.2-2).

Экспоненты

Для любых вещественных то, га и а ф 0 имеем

ат+п.

При а 1 функция га н-т- ап монотонно возрастает. Мы будем иногда условно полагать 0° = 1.

Функция га н-т- ап называется показательной функцией, или экс-понентой (exponential). При а > 1 показательная функция растёт быстрее любого полинома: каково бы ни было Ь,

пь

lim - = 0(2.5)

га->оо ап

или, другими словами, пъ = о(ап). Если в качестве основания степени взять число е = 2,71828 ..., то экспоненту можно записать в виде ряда

о Q ОО h .. гг.

е-= 1 + ж+ - + - + ...= >-2.6

2! 3! klv

к=0

где kl = 1 2 3 ... к (см. ниже о факториалах). Для всех вещественных ж выполнено неравенство

ех~1 + х(2.7)

которое обращается в равенство лишь при х = 0. При \х\ 1 можно оценить ех сверху и снизу так:

1 + хех1 + х + х2(2.8)

Можно сказать, что ех = 1 + х + 0(ж2) при ж -> 0, имея в виду соответствующее истолкование обозначения в (в котором га -> оо заменено на ж -> 0).

При всех ж выполнено равенство Нт,,,- (l + -)п = ех.