В теории алгоритмов понятие “алгоритм” обычно уточняется посредством описания “математической модели” вычислительной машины. Здесь возможны два подхода в зависимости от того, оценивается ли сложность алгоритма (машины, программы) или способность вычислительного процесса, протекающего в соответствии с алгоритмом.
В качестве меры сложности алгоритмов рассматривается функционал, соотносящий каждому алгоритму А некоторое число (А (Л), характеризующее (в подходящем смысле) его громоздкость, например: число команд в А, длина записи А, или какой-нибудь другой числовой параметр, характеризу оритма принимает лишь натуральное значение, поэтому для каждой вычислимой функции существует вычисляющий ее алгоритм с минимальной сложностью. Эту минимальную сложность естественно рассматривать как сложность самой функции, тем самым и множество всех зависимых функций упорядочено по степени сложности этих функций.
Если же исходной является мера сложности вычислений, то получается иная картина. Две сигнализирующие функции могут оказаться несравнимыми, даже если считать, как обычно это принято, что сигнализирующая s а меньше сигнализирующей s в, если для всех а, за исключением, быть может, конечного их числа s а (а) < < s в (а). Поэтому коль скоро зафиксирована некоторая функция f, то априори не ясно, существует ли для нее наилучшее вычисление. Здесь приходится по существу ограничиваться более слабой характеристикой сложности самой функции f , а именно отыскиваются две функции j 1 (нижняя оценка) и j 2 (верхняя оценка), такие, что:
1) существует алгоритм А1, вычисляющий f с сигнализирующей, не превосходящей j 2;
2) каков бы ни был алгоритм А, вычисляющий f , его сигнализирующая не меньше j 1.
Разумеется, чем ближе друг к другу верхняя и нижняя оценки j 1 и j 2, тем точнее охарактеризована сложность самой функции f .
Итак, в отличие от иерархий, основанных на сложности алгоритмов, иерархии, основанные на мере сложности вычислений, являются частично упорядоченными. Это усложняет их изучение, но вместе с тем позволяет, по-видимому, более тонко улавливать сущность того, что мы интуитивно понимаем под сложностью вычислений функции.Теория сложности зависит от положенных в её основу концепций алгоритма а также от выбранной меры сложности алгоритма .