Структуры данных и модели вычислений
Классы функций, используемые для оценки сложности алгоритмов
Все функции, используемые ниже для оценки сложности алгоритмов, считаются асимптотически неотрицательными функциями натурального аргумента, то есть неотрицательными, начиная с некоторого значения аргумента .
Для асимптотических оценок сверху используется класс функций
Для асимптотических оценок снизу используется класс функций
Для асимптотически точных оценок используется класс функций
Очевидно, что справедливы следующие соотношения
Далее, предполагается знание стандартных функций, используемых при оценках сложности, таких как полиномы, экспоненты, суперэкспоненты, логарифмы, суперлогарифмы, факториалы, числа Фибоначчи. Предполагается умение сравнивать их по скоростям роста.
