Трудоемкость алгоритмов и временные оценки

ГОСУДАРСТВЕННОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«БЕЛОРУССКО-РОССИЙСКИЙ УНИВЕРСИТЕТ»

Кафедра «Автоматизированные системы управления»

Реферат на тему:

«ТРУДОЕМКОСТЬ АЛГОРИТМОВ И ВРЕМЕННЫЕ ОЦЕНКИ»

по дисциплине

«Математическая логика и теория алгоритмов»

Выполнил: ______________

Проверил: ______________

Могилев, 2010

СОДЕРЖАНИЕ

1 Элементарные операции в языке записи алгоритмов

2 Примеры анализа простых алгоритмов

3 Переход к временным оценкам

4 Пример пооперационного временного анализа

1 ЭЛЕМЕНТАРНЫЕ ОПЕРАЦИИ В ЯЗЫКЕ ЗАПИСИ АЛГОРИТМОВ

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

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

1) Простое присваивание: а b;

2) Одномерная индексация a[i] : (адрес (a)+i*длинна элемента);

3) Арифметические операции: (*, /, -, +);

4) Операции сравнения: a < b;

5) Логические операции (l1) {or, and, not} (l2);

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

А) Конструкция «Следование»

Трудоемкость конструкции есть сумма трудоемкостей блоков, следующих друг за другом.

F _{«следование»} = f₁ + … + f_k,

где k - количество блоков.

B) Конструкция «Ветвление»

if ( l ) then

f_then с вероятностью p

else

f_else с вероятностью (1-p)

Общая трудоемкость конструкции «Ветвление» требует анализа вероятности выполнения переходов на блоки «Then» и «Else», определяется:

F _{«ветвление»} = f_then * p + f_else * (1-p).

C) Конструкция «Цикл»

После сведения конструкции к элементарным операциям ее трудоемкость определяется как:

F _«цикл» = 1+3*N+N*f_{«тела цикла»}

2 ПРИМЕРЫ АНАЛИЗА ПРОСТЫХ АЛГОРИТМОВ

Пример 1 Задача суммирования элементов квадратной матрицы SumM (A, n; Sum)

Sum 0

For i 1 to n

For j 1 to n

Sum Sum + A[i,j]

end for

Return (Sum)

End

Алгоритм выполняет одинаковое количество операций при фиксированном значении n, и следовательно является количественно-зависимым. Применение методики анализа конструкции «Цикл » дает:

F_A(n)=1+1+ n *(3+1+ n *(3+4))=7 n ²+4* n +2 = (n ²),

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

Пример 2 Задача поиска максимума в массиве MaxS (S,n; Max)

Max S[1]

For i 2 to n

if Max < S[i]

then Max S[i]

end for

return Max

End

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

А) Худший случай. Максимальное количество переприсваиваний максимума (на каждом проходе цикла) будет в том случае, если элементы массива отсортированы по возрастанию. Трудоемкость алгоритма в этом случае равна:

F_A^{^}(n)=1+1+1+ (n-1) (3+2+2)=7 n - 4 = (n).

Б) Лучший случай. Минимальное количество переприсваивания максимума (ни одного на каждом проходе цикла) будет в том случае, если максимальный элемент расположен на первом месте в массиве. Трудоемкость алгоритма в этом случае равна:

F_A(n)=1+1+1+ (n-1) (3+2)=5 n - 2 = (n).

В) Средний случай. Алгоритм поиска максимума последовательно перебирает элементы массива, сравнивая текущий элемент массива с текущим значением максимума. На очередном шаге, когда просматривается к-ый элемент массива, переприсваивание максимума произойдет, если в подмассиве из первых к элементов максимальным элементом является последний. Очевидно, что в случае равномерного распределения исходных данных, вероятность того, что максимальный из к элементов расположен в определенной (последней) позиции равна 1/к. Тогда в массиве из n элементов общее количество операций переприсваивания максимума определяется как:

Величина Hn называется n-ым гармоническим числом. Таким образом, точное значение (математическое ожидание) среднего количества операций присваивания в алгоритме поиска максимума в массиве из n элементов определяется величиной Hn (на бесконечности количества испытаний), тогда:

F_A(n)=1 + (n-1) (3+2) + 2 (Ln(n) + )=5 n +2 Ln(n) - 4 +2 = (n).

3 ПЕРЕХОД К ВРЕМЕННЫМ ОЦЕНКАМ

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

Дано: F_A(D_A) - трудоёмкость алгоритма, требуется определить время работы программной реализации алгоритма - T_A(D_A).

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

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

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

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

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

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

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

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

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

T_A(N) = F_aопi(N) * t _опi

2) Метод Гиббсона. Метод предполагает проведение совокупного анализа по трудоемкости и переход к временным оценкам на основе принадлежности решаемой задачи к одному из следующих типов:

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

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

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

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

Рисунок 5.1 - Возможный вид частотной встречаемости операций

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

T_A(N) = F_A(N) *t _{тип задачи}

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

t_а= T_э(N_э) / F_A(N_э), T(N) = t_а * F_A(N).

4 ПРИМЕР ПООПЕРАЦИОННОГО ВРЕМЕННОГО АНАЛИЗА

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

(a+bi)*(c+di)=(ac - bd) + i(ad + bc)=e + if

1. Алгоритм А1 (прямое вычисление e, f - четыре умножения) MultComplex1 (a, b, c, d; e, f)



2. Алгоритм А2 (вычисление e, f за три умножения) MultComplex2 (a, b, c, d; e, f)

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

По совокупному количеству элементарных операций алгоритм А2 уступает алгоритму А1, однако в реальных компьютерах операция умножения требует большего времени, чем операция сложения, и можно путем пооперационного анализа ответить на вопрос: при каких условиях алгоритм А2 предпочтительнее алгоритма А1?

Введем параметры q и r, устанавливающие соотношения между временами выполнения операции умножения, сложения и присваивания для операндов действительного типа. Тогда мы можем привести временные оценки двух алгоритмов к времени выполнения операции сложения/вычитания - t₊:

t_* = q*t₊, q>1;

t=r*t₊, r<1,

тогда приведенные к t₊ временные оценки имеют вид:

Т_A1 = 4*q*t₊+2*t₊+2*r*t₊=t₊*(4*q+2+2*r);

Т_A2 = 3*q*t₊+5*t₊+5*r*t₊=t₊*(3*q+5+5*r).

Равенство времен будет достигнуто при условии:

4*q+2+2*r = 3*q+5+5*r, откуда:

q = 3 + 3r

и следовательно при

q > 3 + 3r алгоритм А2 будет работать более эффективно.

Таким образом, если среда реализации алгоритмов А1 и А2 - язык программирования, обслуживающий его компилятор и компьютер на котором реализуется задача - такова, что время выполнения операции умножения двух действительных чисел более чем втрое превышает время сложения двух действительных чисел, в предположении, что r << 1, а это реальное соотношение, то для реализации более предпочтителен алгоритм А2.

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

T = (q - 3 - 3*r)* t₊