Торубаров С.И., асс. Козаченко А.А.

Национальный горный университет, Украина

Оценка времени выполнения алгоритма на основе его теоретической вычислительной сложности.

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

Основные понятия

Вычислительная сложность алгоритма — это функция, определяющая зависимость объёма работы, выполняемой некоторым алгоритмом, от размера входных данных. Объём работы обычно измеряется абстрактными понятиями времени и пространства, называемыми вычислительными ресурсами. Время определяется количеством элементарных шагов, необходимых для решения проблемы, тогда как пространство определяется объёмом памяти или места на носителе данных [1]. Таким образом, в этой области предпринимается попытка ответить на центральный вопрос разработки алгоритмов: «как изменится время исполнения и объём занятой памяти в зависимости от размера входа и выхода?».

Формальная постановка задачи

Пусть дано F_a(D_A) - трудоёмкость алгоритма. Требуется определить время работы программной реализации алгоритма – T_A(D_A).

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

На пути построения временных оценок мы сталкиваемся с целым набором различных проблем, пофакторный учет которых вызывает существенные трудности.

Укажем основные из этих проблем [3]:

· неадекватность формальной системы записи алгоритма и реальной системы команд процессора;

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

· различные времена выполнения реальных машинных команд;

· различие во времени выполнения одной команды, в зависимости от значений операндов;

· различные времена реального выполнения однородных команд в зависимости от типов данных;

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

Попытки различного подхода к учету этих факторов привели к появлению разнообразных методик перехода к временным оценкам.

Идея пооперационного анализа состоит в получении пооперационной функции трудоемкости для каждой из используемых алгоритмом элементарных операций с учетом типов данных. Следующим шагом является экспериментальное определение среднего времени выполнения данной элементарной операции на конкретной вычислительной машине [2]. Ожидаемое время выполнения рассчитывается как сумма произведений пооперационной трудоемкости на средние времена операций:

Другой подход предлагается в методе Гиббсона [3]. Данный метод предполагает проведение совокупного анализа по трудоемкости и переход к временным оценкам на основе принадлежности решаемой задачи к одному из следующих типов:

· задачи научно-технического характера с преобладанием операций с операндами действительного типа.

· задачи дискретной математики с преобладанием операций с операндами целого типа.

· задачи баз данных с преобладанием операций с операндами строкового типа.

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

(рис. 1 - Возможный вид частотной встречаемости операций)

На основе полученной информации оценивается общее время работы алгоритма в виде:

Наконец, рассмотрим метод прямого определения среднего времени[4]. В этом методе так же проводится совокупный анализ по трудоемкости – определяется F_a(N), после чего на основе прямого эксперимента для различных значений N определяется среднее время работы данной программы T и на основе известной функции трудоемкости рассчитывается среднее время на обобщенную элементарную операцию, порождаемое данным алгоритмом, компилятором и компьютером – . Эти данные могут быть (в предположении об устойчивости среднего времени по N) интерполированы или экстраполированы на другие значения размерности задачи.

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

Список литературы

1. Т. Кормен, Алгоритмы: построение и анализ. - М.: Вильямс, 2011. - 1296 с.

2. Седжвик Р., Фундаментальные алгоритмы. - М.: DiaSoft, 2001. - 688 с.

3. Кривенцов А.С,. Доверительная трудоемкость компьютерных алгоритмов, разработка оценки и методика определения. - М.: Московский государственный университет приборостроения и информатики, 2012. - 22 c.

4. Ульянов М.В., Шептунов М.В. Математическая логика и теория алгоритмов, часть 2: Теория алгоритмов. – М.: МГАПИ, 2003. – 80 с.