logo search

Понятие алгоритма. Методы оценки алгоритмической сложности.

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

Эффективность – возможность исполнения предписаний за конечное время. Например, алгоритм – процедура, состоящая из “конечного числа команд, каждая из которых выполняется механически за фиксированное время и с фиксированными затратами”. Функция алгоритмически эффективно вычислима, если существует механическая процедура, следуя которой для конкретных значений ее аргументов можно найти значение этой функции.

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

Конечность – выполнение алгоритма при конкретных исходных данных за конечное число шагов.

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

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

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

Таким образом, соединяют математическое, формальное определение алгоритма и конструктивное, позволяющее реализовать модели вычислительными машинами. Алгоритмические вычисления применяются во всех областях науки и техники – монография Д. Кнута рассматривает разнообразные проблемно-ориентированные алгоритмические решения. Графический интуитивный метод построения алгоритмов в виде схем и диаграмм сохраняет актуальность, поддерживается стандартами на языки редактирования. Объектно-ориентированное обобщение алгоритмических языков позволяет активизировать алгоритмическое мышление и организовать масштабное программирование, опираясь на огромные ресурсы производительности и объемы памяти ЭВМ, постоянно наращиваемые стандартные библиотеки.

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

- конечные автоматы;

- машина Тьюринга;

- машина Поста;

- ассоциативное исчисление или нормальные алгоритмы Маркова;

- рекурсивные функции.

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

Сложность алгоритма — характеристика алгоритма, определяющая зависимость времени работы программы от объема обрабатываемых данных.

Для алгоритма обработки равных по объему данных продолжительность его работы является неизменной, а сложность алгоритма — постоянной. При этом время работы алгоритма обработки массивов данных зависит от размеров этих массивов.

Так, если время работы алгоритма по выполнению только операции чтения и занесения данных в оперативную память определяется выражением an+b, где а — время чтения и занесения в память одной информационной единицы, b — время выполнения вспомогательных функций, n — общее количество элементов исходных (входных данных) алгоритма (количество строк таблицы, количество переборов, сочетаний и др.), характеризующим линейную зависимость от n, то сложность такого алгоритма будет линейной. Например, для алгоритма обменной сортировки (сортировка по методу пузырька) n элементов списка сравнений позволяет определить число сравнений, выражаемое полиномом второй степени: (n2 - n) / 2. При этом сложность алгоритма будет квадратичной. Если сложность такого алгоритма оценивается для готовой программы, то вместо числа сравнений вычисляется число внутренних циклов, являющихся основой рассматриваемой программы.

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

Если рассмотреть пример алгоритма перемножения двух матриц размером n×n, то число реализаций оператора внутреннего цикла будет равно n3, а в соответствии с определением произведения матриц минимальное время работы также пропорционально n3. Таким образом, рассмотренные алгоритмы имеют полиномиальную оценку времени работы: n2 и n3. При этом алгоритм с оценкой n2 работает быстрее алгоритма с оценкой n3. С учетом рассмотренных примеров можно представить следующее содержание формальной сложности алгоритма.

Сложность алгоритма — свойство алгоритма, которое определяется как порядок функции, выражающей время его работы.

Так, функции f(n) и g(n), а, следовательно, и сложность алгоритмов будут одного порядка, если для больших n существует константа k, такая, что f(n)/g(n)≤k, то есть f(n)=O(g(n)). Таким образом, сложность алгоритма оценивается функцией изменения времени его выполнения. Для обозначения этой характеристики сложности принято понятие «временная сложность алгоритма», которая описывается функцией скорости роста времени выполнения и обозначается через известную O-символику.

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

  1. Временная сложность алгоритма программы;

  2. Качество скомпилированного кода исполняемой программы;

  3. Машинные инструкции, используемые для выполнения программы.

Наличие второго и третьего факторов не позволяют применять типовые единицы измерения временной сложности алгоритма (секунды, миллисекунды и т. п.), так как можно получить самые различные оценки для одного и того же алгоритма, если использовать разных программистов (которые программируют алгоритм каждый по-своему), разные компиляторы и разные вычислительные машины.

Существует метод, позволяющий теоретически оценить время выполнения алгоритма.

Часто временная сложность алгоритма зависит от количества входных данных. Обычно говорят, что временная сложность алгоритма имеет порядок T(n) от входных данных размера n. Точно определить величину T(n) на практике представляется довольно трудно. Поэтому прибегают к асимптотическим отношениям с использованием О-символики.

Временная сложность алгоритма — «время» выполнения алгоритма, выполняемое в шагах (инструкциях алгоритма), которые необходимо выполнить алгоритму для достижения запланированного результата.