Алгоритмы и их сложность.

Алгоритм — это метод решения некоторого класса задач. Ресурсы, используемые алгоритмом для решения одной такой задачи, называются сложностью алгоритма и измеряются в соответствующих единицах (время счета или используемая память). В данной книге мы интересуемся только временной сложностью вычислений и будем измерять ее, выражал время вычислений в виде функции от некоторой меры (определенной ниже) количества данных, подаваемых на вход.

Определение 1.2.1. Пусть — вещественнозначные функции, определенные на множестве S. Мы будем говорить, что доминируетея функцией , и писать если существуют положительное вещественное число и элемент , такие, что для всех доминирует , и писать если доминируется и (3) функции кодоминантны, и писать , если

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

Определение целого числа i мы будем называть число -цифр в его представлении и будем обозначать ее . Если — потолок, наименьшее целое большее или равное — пол — наибольшее целое число меньшее или равное , то

Пример. Целое число на рис. 1.2.1 при имеет , т.е. длина целого числа — это количество компьютерных ячеек, требующееся для его представления. В дальнейшем индекс (3 мы будем опускать, поскольку для любого другого основания у имеем (если рассматривать как функции, определенные на множестве целых чисел).

Определение 1.2.3. Пусть А — алгоритм и S — множество допустимых значений входа для А. Целое число для число базисных операций, выполняемых алгоритмом А при значении входа — называется функцией времени вычислений, ассоциированной с А и определенной на S. К базисным операциям относятся такие, как сложение и умножение одинарной точности, замены, безусловные передачи управления и вызовы подпрограмм.

Формально полиномы определяются в гл. 3; в сформулированной ниже теореме мы предполагаем, что читатель имеет о них интуитивное представление.

Теорема 1.2.4. Если — полином степени то

Доказательство. Полагая , имеем

Для доказательства теоремы достаточно теперь положить

В качестве применения теоремы 1.2.4 рассмотрим алгоритм, содержащий к инструкций (или шагов), каждая из которых выполняется за время . Тогда весь алгоритм выполняется за время , где — максимум чисел .

Если функция времени вычислений алгоритма А имеет вид или и т.д., где — размер входа (т.е. если функция времени вычислений является самое большее полиномиальной функцией от величины входных данных), то А называется алгоритмом, полиномиальным по времени. Существуют также экспоненциальные по времени алгоритмы, функции времени вычислений которых являются показательными функциями от

количества входных данных, т.е. функциями вида Очевидно, что

и общее правило состоит в том, что вычисление является «легким», если мы имеем дело с полиномиальным по времени алгоритмом, и «сложным», если мы имеем дело с экспоненциальным по времени алгоритмом.

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