функций по порядку; одна функция будет „клевать" другую в соответствии со своим асимптотическим ростом. В этой цепочке встретятся, например, такие члены:
(Здесь
и
— произвольные константы, удовлетворяющие условию
)
Все перечисленные выше функции, за исключением 1, стремятся к бесконечности при
стремящемся к бесконечности. Таким образом, пытаясь вставить в эту иерархию новую функцию, мы не будем стараться определить, стремится ли она к бесконечности; вместо этого нас будет интересовать, как быстро она стремится.
Занимаясь асимптотическим анализом, не следует мелочиться: представляя себе переменную, которая стремится к бесконечности, надо думать о главном. Так, например, из приведенной выше иерархии получаем
это может показаться неверным, если мы ограничимся совсем малюсенькими числами вроде одного гугола,
Действительно, в этом случае
тогда как
есть всего лишь 10°
Но если подняться до числа гуголплекс,
то
бледнеет в сравнении с
Даже если
чрезвычайно мало (меньше, скажем,
величина
будет значительно меньше, чем
если только
достаточно велико. Действительно, если положить
где к выбрано так, чтобы
то будем иметь
но
Таким образом, отношение
стремится к нулю при
Рассмотренная выше иерархия касается функций, стремящихся к бесконечности. Нередко, однако, нас интересуют функции, стремящиеся к нулю, так что было бы неплохо иметь аналогичную иерархию и для таких функций. Мы построим ее, перейдя к обратным величинам, ибо если
никогда не обращаются в нуль, то
Так, все следующие функции (за исключением 1) стремятся к нулю:
Рассмотрим еще несколько функций и попробуем вставить их в иерархию. Число
простых чисел, не превосходящих
как известно, равно приблизительно
Поскольку
умножение на
дает
Соотношение (9.4) можно обобщить. Например,
Здесь
означает лексикографический порядок (порядок слов в словарях); иначе говоря, это неравенство означает, что
или
или же
А как обстоят дела с функцией
где ее место в иерархии? Ответ на подобные вопросы можно получить с помощью правила
которое в два шага получается из определения (9.3) путем логарифмирования. Следовательно,
А поскольку
в
получаем
.
Если две функции
имеют один и тот
порядок роста, мы будем писать
„Официальное" определение таково:
Это имеет место, если, например,
— константа, а
Мы вскоре докажем справедливость этого соотношения во всех случаях, когда
— многочлены одинаковых степеней. Существует и более сильное отношение, определяемое правилом
В таких случаях будем говорить, что
есть асимптотика для
Г. X. Харди [333] ввел интересное и важное понятие — класс логарифмически-экспоненциалъных функций, определяемый рекурсивно как наименьшее семейство
функций, удовлетворяющее следующим условиям:
• Постоянная функция
лежит в
для всех вещественных а.
• Тождественная функция
лежит в
.
• Если
из
, то и
лежит в
.
• Если
из
, то
лежит в
.
• Если функция
из
является „по-существу положительной", то
лежит в
.
Функция
называется
-существу положительной! если существует число по, такое, что
для всех
Используя эти правила, можно, например, показать, что
лежит в
, если
находятся там же. Действительно,
Если
по-существу положительные элементы
, то их произведение
и частное
также лежат в
; то же верно для функций вроде
Харди доказал, что всякая логарифмически-экспоненциальная функция является по-существу положительной, по-существу отрицательной или тождественно равна нулю. Следовательно, произведение и частное любых двух
-функций лежат в
, за исключением случая деления на тождественно нулевую функцию.
Главная теорема Харди о логарифмически-экспоненциальных функциях заключается в том, что эти функции образуют асимптотическую иерархию: если
— любые функции из
, то либо
либо
либо
. В последнем случае найдется константа а, такая, что
Доказательство теоремы Харди выходит за рамки этой книги; но полезно просто знать о существовании этой теоремы, поскольку почти все функции, с которыми нам придется встретиться, лежат в
. На практике мы в большинстве случаев сможем без особого труда вставить данную функцию в данную иерархию.