На этом шаге мы рассмотрим понятие о сложности алгоритма.

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

Такой подход сложился исторически и ориентируется прежде всего на научные и инженерные приложения теории алгоритмов: объемы данных значительно превышают размеры самой программы, а программа может выполняться несколько часов. Если не считать офисных и бухгалтерских применений вычислительных машин, то производительность и объем памяти компьютера никогда не казались программистам чрезмерными и постоянной задачей является сделать программу работающей хотя бы немного быстрее и попытаться заставить ее работать в стесненных условиях ограниченного поля памяти.

Если в научных и инженерных приложениях большое время вычислений доставляет лишь неудобство пользователям, то в ряде других областей ресурсы настолько критичны, что может возникнуть проблема целесообразности всего проекта из-за неэффективной работы программы. К таким областям относятся системы реального времени (real-time systems). Это основанные на компьютерах системы, которые управляют процессами в реальном мире или обрабатывают информацию, служащую для принятия оперативных решений. Примерами систем реального времени являются бортовые компьютерные системы космических кораблей, самолетов, других транспортных средств; компьютерные системы, управляющие непрерывным химическим производством, ядерными реакторами; системы противовоздушной обороны, управления огнем и др.

В данном разделе будут рассмотрены две характеристики сложности алгоритмов - временная и емкостная. Не будем обсуждать сложность (длину) текста алгоритма, поскольку она больше характеризует исполнителя (машину), его язык, а не метод решения задачи. Не будем также обсуждать логическую сложность разработки алгоритма - сколько человеко-месяцев нужно потратить на создание программы, поскольку не представляется возможным дать объективные количественные характеристики. Обе эти темы относятся к области компьютерных наук, называемой "технология программирования" (software engineering).

Единицы измерения сложности будем привязывать к классу архитектур наиболее распространенных ЭВМ. Временную сложность будем подсчитывать в исполняемых командах: количество арифметических операций, количество сравнений, пересылок (в зависимости от алгоритма). Емкостная сложность будет определяться количеством скалярных переменных, элементов массивов, элементов записей или просто количеством байт.

Одно из свойств алгоритма - массовость. В общем случае количество операций и требуемая память зависят от исходных данных, т.е. являются функциями вектора X = (х₁, х₂, ..., х_n) исходных данных. С точки зрения математического анализа сложности, сравнения алгоритмов, их классификации хотелось бы, чтобы функции сложности (x₁, x₂, ..., x_n) выражались в виде формул с использованием обычных, элементарных математических функций. Тогда в нашем распоряжении оказался бы богатый арсенал средств классической математики. Но это не всегда возможно, так как исходные данные могут быть нечисловыми (графы, географические карты, строки символов, звуки и т. д.). Поэтому сложность алгоритма a рассматривается как функция от некоторого интегрированного числового параметра V, характеризующего исходные данные. Обозначим: Tα(V) - временная сложность алгоритма α; Sα(V) - емкостная сложность.

Параметр V, характеризующий данные, называют иногда объемом данных или сложностью данных. Оба эти термина не совсем точны. Выбор параметра V зависит не только от вида данных, но и от вида алгоритма или от задачи, которую этот алгоритм решает.

Рассмотрим два примера.

Задача вычисления факториала числа x (x>0). Программа итеративного решения задачи имеет следующий вид:
```
    function Factorial (х: integer): integer;
    var 
      m, i: integer;
    begin 
      m := 1;
      for i := 2 to x do 
        m := m*i;
      Factorial := m;
    end;
```
Количество операций здесь подсчитывается легко: один раз выполняется оператор m := 1; тело цикла (умножение и присваивание) выполняется (х-1) раз; один раз выполняется присваивание Factorial := m. Если сложность каждой из элементарных операций считать равной единице, то временная сложность приведенного алгоритма будет равна 1+2(x-1)+1=2х. Из этого анализа ясно, что за параметр V удобно принять значение х.
Задача отыскания скалярного произведения двух векторов A = (a₁, a₂, ... , a_k), В = (b₁, b₂, ..., b_k). Вектор входных данных X = (А, В), n = 2k. Стандартный алгоритм циклического сложения попарных произведений компонент векторов выполняет пропорциональное k число операций, т.е. можно взять V = k = n/2. Зависимости сложности алгоритма от значений a_i и b_i нет, имеется лишь зависимость от количества компонент.

Эти два примера иллюстрируют ситуации, когда для оценки сложности важны значения исходных данных (1) и количество исходных данных (2). Первая ситуация является более общей, так как k во втором примере фактически тоже входит в перечень исходных данных. Однако второй пример показывает, что от некоторых исходных данных сложность алгоритма может не зависеть. Собственно говоря, для анализа сложности не всегда можно сформулировать интегральный параметр V и лишь после построения оценки становится ясно, какая характеристика исходных данных является значимой для данного алгоритма.

Отыскание функций сложности алгоритмов важно как с прикладной, так и с теоретической точек зрения.

В практике проектирования систем реального времени задача разработки программы формулируется так: отыскать такой алгоритм a, решающий задачу P, что Тα(X) < Tmax при X ∈ D, где D - область допустимых значений входных данных (задача с ограничением на временную сложность).

В системах, где критерий качества связан с временем ожидания реакции компьютера (системы управления базами данных, системы автоматического перевода для естественных языков программы для игры в шахматы и другие) задача может быть поставлена так: отыскать среди всех алгоритмов, решающих задачу Р, такой алгоритм а, для которого функция Tα(X) будет принимать минимальные значения на выбранном подмножестве S значений исходных данных, X ∈ S ⊂ D (задача минимизации временной сложности; дополнительно формулируются ограничения по емкостной сложности).

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

С теоретической точки зрения важным является вопрос: как далеко для данной задачи можно продвигаться по пути совершенствования (уменьшения сложности) алгоритмов ее решения, когда наступает предел, свойственный самой задаче, далее которого попытки совершенствования алгоритмов заведомо не приведут к успеху?

Другой интересный вопрос связан с классификацией алгоритмов. Числовая функция Tα(V) растет (обычно) с возрастанием значений аргумента V. Как быстро она растет? Существуют алгоритмы с линейной зависимостью временной сложности от объема данных, со сложностью, возрастающей пропорционально квадрату V, более высоким степеням V. Такие алгоритмы называются полиномиальными. А существуют алгоритмы, сложность которых увеличивается быстрее любого полинома. Ясно, что с точки зрения возможностей реализации они значительно отличаются друг от друга. Поэтому очень много исследований посвящено вопросам типа "возможен ли для данной задачи полиномиальный алгоритм"?

На следующем шаге мы рассмотрим верхние и средние оценки сложности алгоритмов.

Содержание Следующий шаг