Приложение A: Асимптотическая запись

В этом приложении определяются некоторые способы записи, широко используемые при изучении асимптотических свойств алгоритмов. Более тщательное рассмотрение этого предмета можно найти у Грэхэма, Кнута и Паташника [Graham, Knuth, Patashnik, 1990].

Для классификации некоторых функций от n часто применяется понятие относительной скорости, с которой при возрастании n эти функции стремятся к бесконечности. Для этой цели можно использовать определенный ниже оператор отношения, введенный Полем дю Буа-Реймоном [Paul du Bois-Reymond, 1981].

Использование этого оператора демонстрируется в следующей асимптотической иерархии

1log nn^an^bbⁿ,

где a и b – константы, такие, что 0 < a < 1 < b.

Кроме того, применяется запись «O большое», введенная Паулем Бахманом [Paul Bachman, 1894], которая удобна для выражения ограничений сверху. Она определяется следующим образом.

f(n) = O(g(n)) |f(n)| c|g(n)|, для некоторого постоянного c > 0

(B.2)

Обратите внимание, что в выражениях приведенного выше типа принято использовать знак ‘=’. Однако, он не обозначает равенства, и должен читаться как ‘является’ (несимметричный), а не ‘равно’ (симметричный). Иногда неявно подразумевается, что подобное отношение справедливо при достаточно больших n, то есть при . В этом случае строгим условием является

при nn0 для некоторой константы n0

(B.3)

Соответствующей записью ограничений снизу является «Омега большое». Она определяется следующим образом.

для некоторой константы c > 0

(B.4)

Если g(n) является нижней границей для f(n), то f(n) должна быть верхней границей g(n), то есть,

И наконец, для указания точной степени роста используется «Тета большое», то есть: