9.1 ИЕРАРХИЯ

Встречающиеся на практике функции от имеют различную „асимптотическую скорость роста"; некоторые функции стремятся к бесконечности быстрее других. Мы формализуем это понятие с помощью определения

Введенное отношение транзитивно: если то Можно также писать если Эти обозначения ввел в 1871 г. Поль Дюбуа-Рай-мон [113].

Например, неформально мы говорим, что растет медленнее, чем . В действительности

для произвольных вещественных и (3.

Разумеется, существует много функций, помимо степеней Отношение можно использовать, чтобы расставить множество

функций по порядку; одна функция будет „клевать" другую в соответствии со своим асимптотическим ростом. В этой цепочке встретятся, например, такие члены:

(Здесь и — произвольные константы, удовлетворяющие условию )

Все перечисленные выше функции, за исключением 1, стремятся к бесконечности при стремящемся к бесконечности. Таким образом, пытаясь вставить в эту иерархию новую функцию, мы не будем стараться определить, стремится ли она к бесконечности; вместо этого нас будет интересовать, как быстро она стремится.

Занимаясь асимптотическим анализом, не следует мелочиться: представляя себе переменную, которая стремится к бесконечности, надо думать о главном. Так, например, из приведенной выше иерархии получаем это может показаться неверным, если мы ограничимся совсем малюсенькими числами вроде одного гугола, Действительно, в этом случае тогда как есть всего лишь 10° Но если подняться до числа гуголплекс, то бледнеет в сравнении с

Даже если чрезвычайно мало (меньше, скажем, величина будет значительно меньше, чем если только достаточно велико. Действительно, если положить где к выбрано так, чтобы то будем иметь но Таким образом, отношение стремится к нулю при

Рассмотренная выше иерархия касается функций, стремящихся к бесконечности. Нередко, однако, нас интересуют функции, стремящиеся к нулю, так что было бы неплохо иметь аналогичную иерархию и для таких функций. Мы построим ее, перейдя к обратным величинам, ибо если никогда не обращаются в нуль, то

Так, все следующие функции (за исключением 1) стремятся к нулю:

Рассмотрим еще несколько функций и попробуем вставить их в иерархию. Число простых чисел, не превосходящих как известно, равно приблизительно Поскольку умножение на дает

Соотношение (9.4) можно обобщить. Например,

Здесь означает лексикографический порядок (порядок слов в словарях); иначе говоря, это неравенство означает, что или или же

А как обстоят дела с функцией где ее место в иерархии? Ответ на подобные вопросы можно получить с помощью правила

которое в два шага получается из определения (9.3) путем логарифмирования. Следовательно,

А поскольку в получаем .

Если две функции имеют один и тот порядок роста, мы будем писать „Официальное" определение таково:

Это имеет место, если, например, — константа, а Мы вскоре докажем справедливость этого соотношения во всех случаях, когда — многочлены одинаковых степеней. Существует и более сильное отношение, определяемое правилом

В таких случаях будем говорить, что есть асимптотика для

Г. X. Харди [333] ввел интересное и важное понятие — класс логарифмически-экспоненциалъных функций, определяемый рекурсивно как наименьшее семейство функций, удовлетворяющее следующим условиям:

• Постоянная функция лежит в для всех вещественных а.

• Тождественная функция лежит в .

• Если из , то и лежит в .

• Если из , то лежит в .

• Если функция из является „по-существу положительной", то лежит в .

Функция называется -существу положительной! если существует число по, такое, что для всех

Используя эти правила, можно, например, показать, что лежит в , если находятся там же. Действительно, Если по-существу положительные элементы , то их произведение и частное также лежат в ; то же верно для функций вроде Харди доказал, что всякая логарифмически-экспоненциальная функция является по-существу положительной, по-существу отрицательной или тождественно равна нулю. Следовательно, произведение и частное любых двух -функций лежат в , за исключением случая деления на тождественно нулевую функцию.

Главная теорема Харди о логарифмически-экспоненциальных функциях заключается в том, что эти функции образуют асимптотическую иерархию: если — любые функции из , то либо либо либо . В последнем случае найдется константа а, такая, что

Доказательство теоремы Харди выходит за рамки этой книги; но полезно просто знать о существовании этой теоремы, поскольку почти все функции, с которыми нам придется встретиться, лежат в . На практике мы в большинстве случаев сможем без особого труда вставить данную функцию в данную иерархию.