Логарифмы

Мы будем использовать такие обозначения:

lgra = log2 га(двоичный логарифм),

In га = loge га(натуральный логарифм) lgfcra = (lgra)fc,

lglgra = lg(lgra)(повторный логарифм).

Мы будем считать, что в формулах знак логарифма относится лишь к непосредственно следующему за ним выражению, так что lg га + к есть lg(ra) + к (а не lg(ra + к)). При Ь > 1 функция га \-> logb га (определённая при положительных га) строго возрастает.

Следующие тождества верны при всех а > О, 6 > О, с > 0 и при всех га (если только основания логарифмов не равны 1):

l°g6(l/a) = -log6a

а = 61о§ьа, logc(a&) = logca + logc6, log6an = ralog6a,bgb a = -(2.9)

1

,logea

log6 a = i-г

logc6

jbgbC = clo;

Изменение основания у логарифма умножает его на константу, поэтому в записи типа О (log га) можно не уточнять, каково основание логарифма. Мы будем чаще всего иметь дело с двоичными логарифмами (они появляются, когда задача делится на две части) и потому оставляем за ними обозначение lg.

Для натурального логарифма есть ряд (который сходится при \х\ < 1):

Ж2 у. 3 у. 4 у. 5

1п(1 + ж) = ж---1-----1---...

v 2 3 4 5

При ж > - 1 справедливы неравенства

у- 1п(1 + ж) ж(2.10)

которые обращаются в равенства лишь при ж = 0.

Говорят, что функция /(га) ограничена полилогарифмом (is poly-logaritmically bounded), если /(га) = lg° га. Предел (2.5) после подстановок га = lg т и а = 2е даёт

\gbm \gbm lim ---j-= lim - = 0

m->oo (2C) §m m->oo mc

и, таким образом, lg6 га = o(rac) для любой константы с > 0. Другими словами, любой полином растёт быстрее любого полилогарифма.

Факториалы

Запись га! (читается «эн факториал», "га factorial") обозначает произведение всех чисел от 1 до га. Полагают 0! = 1, так что га! = га • (га - 1)! при всех га = 1, 2, 3,....

Сразу же видно, что га! пп (каждый из сомножителей не больше га). Более точная оценка даётся формулой Стирлинга (Stirlings approximation), которая гласит, что

ra! = V2(-J (1 + 6(1/га))(2.11)

Из формулы Стирлинга следует, что

га! = о(пп), га! = cj(2n), lg(ra!) = O(ralgra).

Справедлива также следующая оценка:

(f га! ег12п.(2.12)

Итерации логарифма

Мы используем обозначение log* га («логарифм со звёздочкой от эн») для функции: называемой итерированным логарифмом (iterated logarithm). Эта функция определяется так. Вначале рассмотрим г-ую итерацию логарифма, функцию lg\ определённую так: lg(°) га = га и lgW(ra) = lg(lg(8 1) га) при г > 0. (Последнее выражение определено, если lg(8 1) га определено и положительно.) Будьте внимательны: обозначения lg8 га и lgW га внешне похожи, но означают совершенно разные функции.

Теперь lg* га определяется как минимальное число г 0, при котором lgW га 1. Другими словами, lg* га - это число раз, которое нужно применить функцию lg, чтобы из га получить число, не превосходящее 1.

Функция lg *га растёт исключительно медленно:

Поскольку число атомов в наблюдаемой части Вселенной оценивается как 1080, что много меньше 265536, то значения га, для которых lg* га > 5, вряд ли могут встретиться.

Числа Фибоначчи

Последовательность чисел Фибоначчи (Fibonacci numbers) определяется рекуррентным соотношением:

F0 = О, Fi = 1, Fi = Fi-t + Fi-2 при г 2(2.13)

Другими словами, в последовательности Фибоначчи

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ...

каждое число равно сумме двух предыдущих. Числа Фибоначчи связаны с так называемым отношением золотого сечения (golden ratio) ip и с сопряжённым с ним числом ф:

1 +

tp= 2 = 1,61803 ..

1 - л/Ъ ф= -- = -0,61803.

(2.14)

Именно, имеет место формула

которую можно доказать по индукции (упр. 2.2-7). Поскольку \ф\ < 1, слагаемое \фг/у/5\ меньше 1/\/Ъ < 1/2, так что Fi равно числу (рг/у/Ъ, округлённому до ближайшего целого.

Число Fi быстро (экспоненциально) растёт с ростом г.

Упражнения

2.2-1 Покажите, что для монотонно возрастающих функций f(n) и д(п) функции f(n) + д(п) и f(g(n)) будут также монотонно возрастать. Если к тому же f(n) и д(п) неотрицательны при всех га, то и функция f(n)g(n) будет монотонно возрастать.

2.2-2 Покажите, что Т(п) = ra°W тогда и только тогда, когда существует положительное /г, при котором Т(п) = 0(пк) (считаем, что Т(п) > 1).

2.2-3 Докажите равенства (2.9).

2.2-4 Докажите, что lg(ra!) = O(ralgra) и что га! = о(пп).

2.2-5* Будет ли функция [lgra]! полиномиально ограниченной? Будет ли функция [lglgra]! полиномиально ограниченной?

2.2-6* Что больше (при больших га): lg(lg*ra) или lg*(lgra)?