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

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

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

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

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

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

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

Пусть F(A) - формальное описание алгоритма, N - объем входных данных (например, длина вектора исходных значений). Необходимо получить математическую зависимость количества выполненных элементарных операций (трудоемкости) от величины N таким образом, чтоб можно было выделить самую существенную составляющую.

В данном случае, конечно, можно просто ориентироваться на результаты работы, но это создает трудности при сравнительном анализе - существует много ловушек, в которые можно попасть, делая выводы о том, какой способ лучше, на основании сравнения времени работы. Во-первых, любая видимая разница может определяться случайностью. Таким образом, всегда будут случайные погрешности и если разница между двумя реализациями не превышает некоторой погрешности, нельзя сказать, что эти реализации различаются (хотя и то, что они одинаковы, тоже нельзя утверждать). Проблема усложняется, если необходимо сравнить больше двух реализаций. Количество пар для сравнения увеличивается пропорционально квадрату количества сравниваемых версий, сильно увеличивая вероятность того, что как минимум две из версий будут казаться слегка различными. (Это называется проблемой множественного сравнения)[3]. Потому целесообразно обратиться к математическому анализу, который позволит в однозначной и понятной формы выразить характеристики алгоритмов.

Большинство алгоритмов имеют главный параметр N, который значительно влияет на время их выполнения. Общей целью является выражение ресурсных требований программ (как правило, времени выполнения) в зависимости от N с использованием математических формул, которые максимально просты и справедливы для больших значений параметров. Обычно алгоритмы имеют время выполнения пропорциональное одной из нескольких функций: постоянное значение (константа), логарифмическая, линейная, линейно-логарифмическая, степенная, показательная [1].

Время выполнения определенной программы, скорее всего, будет некоторой константой, умноженной на один из этих элементов (главный член) плюс меньшие слагаемые. Значения постоянного коэффициента и остальных слагаемых зависят от результатов анализа и деталей реализации. В грубом приближении коэффициент при главном члене связан с количеством инструкций во внутреннем цикле: на любом уровне разработки алгоритма разумно сократить количество таких инструкций. Для больших N доминирует эффект главного члена, для малых N или для тщательно разработанных алгоритмов вклад дают и другие слагаемые, поэтому сравнение алгоритмов становится более сложным[1].

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

наибольшее целое, меньшее или равное х.

: наименьшее целое, большее или равное х.

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

При анализе алгоритмов часто встречается также функция факториал N!. Как и экспоненциальная функция, факториал возникает при лобовом решении задач и растет слишком быстро, чтобы такие решения представляли практический интерес. Она также возникает при анализе алгоритмов, поскольку представляет собой количество способов упорядочения N объектов. Для аппроксимации N! используется формула Стирлинга:

Кроме того, часто возникает дискретизованная версия функции натурального логарифма, называемая гармоническими числами [2]. Например, задача поиска максимума в массиве: алгоритм последовательно перебирает элементы массива, сравнивая текущий элемент массива с текущим значением максимума. На очередном шаге, когда просматривается k-ый элемент массива, переприсваивание максимума произойдет, если в подмассиве из первых k элементов максимальным элементом является последний. Очевидно, что в случае равномерного распределения исходных данных, вероятность того, что максимальный из k элементов расположен в определенной (последней) позиции равна 1/k. Тогда в массиве из N элементов общее количество операций переприсваивания максимума определяется как:

Hn - это N-тое гармоническое число определяется выражением

Натуральный логарифм ln N — это значение площади под кривой между 1 и N;

(Рис. 1 Иллюстрация значения натурального логарифма)

Гармоническое число H_N — это площадь под ступенчатой функцией, которую можно определить, вычисляя значения функции для целых чисел от 1 до N. Формула

где у= 0.57721... (эта константа называется постоянной Эйлера), дает отличное приближение для H_N[2].

Для удобства следует свести формулы для расчета приближенных значений в таблицу:

Таблица 1. Формулы для расчета приближенных значений некоторых функций
Функция	Название	Приближение
	округление снизу	x
	округление сверху	x
lg N	двоичный логарифм	1.44 ln N
FN	числа Фибоначчи
HN	гармонические числа
N!	факториал
lg (N!)		N lg N - 1.44 N

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

Вывод

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

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

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

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

3. Magnus Lie Hetland, Python Algorithms: Mastering Basic Algorithms in the Python Language. - NY.: Apress, 2010 - 320 c.