Учебно-методический комплекс для специальности 1-31 03 07 «Прикладная информатика

ошибку в получаемые результаты.

Основные причины этой ошибки:

различная частотная встречаемость элементарных операций;

Таким образом, возникает задача перехода от функции трудоемкости к

оценке времени работы алгоритма на конкретном процессоре.

Дано: 𝑭(𝑨) - трудоёмкость алгоритма. Требуется определить время работы

программной реализации алгоритма 𝑻(𝑨).

Основные проблемы:

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

системы команд процессора;

наблюдаемое время выполнения программы (конвейер;

кэширование памяти; предвыборка команд, данных и т.д.);

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

различие во времени выполнения однородных (однотипных) команд

в зависимости от значений операндов и типов данных;

неоднозначности компиляции исходного текста, обусловленные как

самим компилятором, так и его настройками.

Методики перехода к временным оценкам:

1. Пооперационный анализ

2. Метод Гиббсона

3. Метод прямого определения среднего времени

1. Пооперационный анализ

1-ый шаг. Получение пооперационной функции трудоемкости для каждой

из элементарных операций с учетом типов данных𝑭𝐀,оп,𝒊 (𝒏).

2-ой шаг. Экспериментальное определение среднего времени выполнения

данной элементарной операции на конкретной вычислительной

машине𝒕оп,𝒊,𝒄𝒑 .

пооперационной трудоемкости на средние времена операций:

Метод предполагает переход к временным оценкам на основе

принадлежности решаемой задачи к одному из следующих типов:

задачи научно-технического характера с преобладанием операций с

операндами действительного типа;

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

операндами целого типа

задачи баз данных с преобладанием операций с операндами

строкового типа

Далее на основе анализа множества реальных программ для решения

соответствующих типов задач определяется частотная встречаемость

операций (рис. 11), создаются соответствующие тестовые программы, и

определяется среднее время на операцию в данном типе задач –

tср.тип.задач.

алгоритма в виде:

В этом методе проводится совокупный анализ по трудоемкости:

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

данных 𝑵;

рассчитывается среднее время на обобщенную элементарную

операцию, порождаемое данным алгоритмом, компилятором и

компьютером:

∑𝒊 𝒕𝑵,𝒊 𝑵оп,𝒊

𝑻ср =

∑𝒊 𝑵оп,𝒊

𝒕𝑨,ср =

𝑻(𝒏) = 𝑭𝑨 (𝒏)𝒕𝑨,ср

задачи при условии устойчивости среднего времени по 𝑵.

применения того или иного алгоритма решения задачи.

Пример. Задача умножения двух комплексных чисел:

A1: (𝒂 + 𝒃 𝒊) ∗ (𝒄 + 𝒅 𝒊) = (𝒂𝒄 − 𝒃𝒅) + 𝒊 (𝒂𝒅 + 𝒃𝒄) = 𝒆 + 𝒊 𝒇

A2: (𝒂 + 𝒃 𝒊) ∗ (𝒄 + 𝒅 𝒊) = 𝒛𝟏 − 𝒛𝟐 + 𝒊 (𝒛𝟏 + 𝒛𝟑 ) = 𝒆 + 𝒊 𝒇,

𝒛𝟏 = 𝒄(𝒂 + 𝒃),𝒛𝟐 = 𝒃 (𝒅 + 𝒄),𝒛𝟑 = 𝒂(𝒅 − 𝒄)

1. Алгоритм А1 (прямое вычисление 𝑒, 𝑓 – 4 умножения)

MultComplex1(a, b, c, d; e, f)

e ←a*c-b*dfA1= 8 операций

f ←a*d+b*cf*= 4 операций

Return(e, f)f+-= 2 операций

End.f←= 2 операций

2. Алгоритм А2 (вычисление 𝑒, 𝑓 за 3 умножения)

32


MultComplex2(a, b, c, d; e, f)

z1 ←c*(a+b)

z2 ←b*(d+c)

z3 ←a*(d-c)fA2= 13 операций

e ←z1-z2f*= 3 операций

f ←z1+z3f+-= 5 операций

Return(e, f)f←= 5 операций

End.

алгоритму А1, однако в реальных компьютерах операция умножения

требует большего времени, чем операция сложения.

Введя параметры 𝒒 и 𝒓, устанавливающие соотношения между временами

выполнения операции умножения и сложения, получим временные оценки

двух алгоритмов к времени выполнения операции сложения/вычитания (𝑡+ ):

𝑡∗ = 𝑞 ∗ 𝑡+ , 𝑞 > 1;

𝑡← = 𝑟 ∗ 𝑡+ , 𝑟 < 1, тогда приведенные к 𝑡+ временные оценки имеют вид:

𝑇𝐴1 = 4 ∗ 𝑞 ∗ 𝑡+ + 2 ∗ 𝑡+ + 2 ∗ 𝑟 ∗ 𝑡+ = 𝑡+ ∗ (4 ∗ 𝑞 + 2 + 2 ∗ 𝑟);

𝑇𝐴2 = 3 ∗ 𝑞 ∗ 𝑡+ + 5 ∗ 𝑡+ 5 ∗ 𝑟 ∗ 𝑡+ = 𝑡+ ∗ (3 ∗ 𝑞 + 5 + 5 ∗ 𝑟).

Равенство времен будет достигнуто при условии 4*q+2+2*r = 3*q+5+5*r,

откудаq = 3 + 3r и, следовательно, при q> 3 + 3r алгоритм А2 будет

работать более эффективно.

∆𝑻 = (𝒒 − 𝟑 − 𝟑 ∗ 𝒓) ∗ 𝒕+

При умножении в прямом коде:

𝑛 – число разрядов множителя,

𝑝𝑖 – вероятность появления 1 в множителе

𝒏

𝒏

𝒕∗ = ∑(𝒕← + 𝒑𝒊 𝒕+ ) = 𝒏𝒕← + 𝒕+ ∑ 𝒑𝒊

𝒊=𝟏

𝒊=𝟏

𝑛

𝑖=1

Худший случай

∑

𝑡𝐴2

𝑝𝑖 = 𝑛, 𝑡→ ≪ 𝑡+

𝑡𝐴1 = 4𝑛(𝑡← + 𝑡+ ) + (𝑡− + 𝑡+ ) + 2𝑡← = (4𝑛 + 2)(𝑡← + 𝑡+ )

= 3𝑛(𝑡← + 𝑡+ ) + 2𝑡− + 3𝑡+ + 5𝑡← = (3𝑛 + 5)(𝑡← + 𝑡+ )

(отсутствуют временные затраты𝑐6 и𝑐7 ):

𝑇(𝑛) = 𝑐1 𝑛 + 𝑐2 (𝑛 − 1) + 𝑐4 (𝑛 − 1) + 𝑐5 (𝑛 − 1) + 𝑐8 (𝑛 − 1)

= (𝑐1 + 𝑐2 + 𝑐4 + 𝑐5 + 𝑐8 )𝑛 − (𝑐2 + 𝑐4 + 𝑐5 + 𝑐8 ).

𝑻(𝒏) = 𝒂(𝒕)𝒏 + 𝒃(𝒕).

Худший случай: когда элементы массива отсортированы в обратном

порядке, 𝑡𝑗 = 𝑗:

𝑛(𝑛 + 1)

− 1,∑ 𝑗 =

2

𝑗=2

𝑛

,

2

𝑛(𝑛 + 1)

𝑇(𝑛) = 𝑐1 𝑛 + 𝑐2 (𝑛 − 1) + 𝑐4 (𝑛 − 1) + 𝑐5 (− 1)

2

𝑛(𝑛 − 1)𝑛(𝑛 − 1)

+ 𝑐6 () + 𝑐7 () + 𝑐8 (𝑛 − 1)

22

𝑐5 𝑐6 𝑐7 2𝑐5 𝑐6 𝑐7

=( ++ ) 𝑛 + (𝑐1 + 𝑐2 + 𝑐4 +−−+ 𝑐8 ) 𝑛

222222

− (𝑐2 + 𝑐4 + 𝑐5 + 𝑐8 ).

𝑻(𝒏) = 𝒂(𝒕)𝒏𝟐 + 𝒃(𝒕)𝒏 + 𝒄(𝒕)

В среднем случае необходимо совершить 𝑗/2 проверок, поэтому оценка та

же.

3.7. ТЕОРЕТИЧЕСКИЙ ПРЕДЕЛ ТРУДОЕМКОСТИ АЛГОРИТМОВ

Дано:

алгоритмически разрешимая задача

множество алгоритмов

Можно получить оценку трудоемкости этих алгоритмов в худшем случае:

𝒇𝒊 (𝑫) = 𝑶(𝒈(𝑫𝒂 )),где 𝑫𝒂 – множество конкретных проблем данной задачи,

𝒊– номер алгоритма.

Вопросы:

существует ли функциональный нижний предел для g(Da)?

35


если «да», то существует ли алгоритм, решающий задачу с такой

трудоемкостью в худшем случае?

какова оценка сложности самого «быстрого» алгоритма решения

задачи в худшем случае?

Ответ на третий вопрос - это оценка самой задачи, а не какого-либо

алгоритма ее решения.

Функциональный теоретический нижний предел трудоемкости задачи в

худшем случае:

𝑭𝑙𝑖𝑚 = 𝐦𝐢𝐧{𝚯(𝑭𝒂 (𝑫))}.

Если можно на основе теоретических рассуждений доказать существование

и получить оценивающую функцию 𝑭𝑙𝑖𝑚 , то можно утверждать, что

любой алгоритм, решающий данную задачу работает не быстрее,

чем с оценкой в худшем случае: 𝑭𝒂 (𝑫) = 𝛀(𝑭𝑙𝑖𝑚 ).

Примеры:

1. Просканировать поверхность требует время, линейно зависящее от его

площади 𝚯(𝑨).

2. Для задачи поиска максимума в массиве𝑨 = (𝒂𝟏 , … , 𝒂𝒏 ) должны быть

просмотрены все элементы, и 𝑭𝑙𝑖𝑚 = 𝚯(𝒏).

3. Задача «найти имя в телефонной книге» требует время, логарифмически

зависящее от количества записей: 𝐎(𝒍𝒐𝒈𝟐 (𝒏)).

4. Для задачи умножения матриц можно сделать предположение, что

необходимо выполнить некоторые арифметические операции со всеми

исходными данными, что приводит к оценке 𝑭𝑙𝑖𝑚 = 𝚯(𝒏𝟐 ).

Лучший алгоритм умножения матриц имеет оценку 𝚯(𝒏𝟐.𝟑𝟕𝟔 ).

Расхождение между теоретическим пределом и оценкой лучшего

известного алгоритма позволяет предположить, что

либо существует, но еще не найден более быстрый алгоритм

умножения матриц,

либо оценка 𝚯(𝒏𝟐 )должна быть доказана, как теоретический предел.

36

Алгоритм Штрассена (1969)

𝑶(𝒏𝐥𝐨𝐠𝟐 𝟕 ) ≈ 𝑶(𝒏𝟐.𝟖𝟎𝟕 )

Если размер умножаемых матриц 𝒏 не является натуральной степенью

двойки, то дополняют исходные матрицы дополнительными нулевыми

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

умножения размеры, но теряют в эффективности за счёт дополнительных

ненужных умножений.

Матрицы A, B и C делятся на равные по размеру блочные матрицы:

Итерационный процесс продолжается n раз до тех пор, пока матрицы 𝐶𝑖,𝑗 не

выродятся в числа.

На практике итерации останавливают при размере матриц от 32 до 128 и

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

Штрассена теряет эффективность по сравнению с обычным на малых

матрицах из-за дополнительных копирований массивов.

Алгоритм Пана (1978): 𝚯(𝒏𝟐.𝟕𝟖𝟎𝟒𝟏 ).

Алгоритм Бини (1979): 𝚯(𝒏𝟐.𝟕𝟕𝟗𝟗 ).

Алгоритмы Шёнхаге (1981): 𝚯(𝒏𝟐.𝟔𝟗𝟓 ), 𝚯(𝒏𝟐.𝟓𝟏𝟔𝟏 ).

Алгоритм Копперсмита-Винограда (1990): 𝚯(𝒏𝟐.𝟑𝟕𝟔 ).

На сегодняшний день алгоритм Копперсмита-Винограда считается

наиболее асимптотически быстрым, но он эффективен только на очень

больших матрицах и поэтому применяется редко.

37


В 2003 Кох и др. рассмотрели в своих работах алгоритмы Штрассена и

Копперсмита-Винограда в контексте теории групп.

Показана возможность существования алгоритмов умножения матриц со

сложностью 𝚯(𝒏𝟐 ).

3.8. РЕКУРРЕНТНЫЕ СООТНОШЕНИЯ

Если алгоритм рекуррентно вызывает сам себя, время его работы можно

описать с помощью рекуррентного соотношения.

Рекуррентное соотношение (recurrence) — это уравнение или

неравенство, описывающее функцию с использованием ее самой, с

меньшими аргументами.

Рекурсия — приём программирования, который позволяет разбивать

задачу на меньшие подзадачи, каждая из которых решаются с помощью

одного и того же алгоритма.

Пример 1.Сортировка слиянием(mergesort) — алгоритм сортировки,

который упорядочивает структуры данных, доступ к элементам которых

можно получать только последовательно (списки, потоки и т.п.) (рис. 1).

Разделение:сортируемая последовательность, состоящая из 𝒏 элементов,

разбивается на две меньшие последовательности, каждая из которых

содержит 𝒏/𝟐 элементов.

Покорение: сортировка каждой полученной последовательности методом

слияния.

Комбинирование:объединениедвухотсортированных

последовательностей для получения окончательного результата.

Рекурсивное разбиение задачи на меньшие подзадачи происходит до тех

пор, пока размер массива не достигнет единицы (любой массив длины 1

можно считать упорядоченным).

Нетривиальным этапом является соединение двух упорядоченных массивов

в один.

Алгоритм слияния (на примере колоды карт):

1. Пусть имеем две стопки карт, лежащих рубашками вниз.

2. В каждой из этих стопок карты идут сверху вниз в неубывающем

порядке.

3. На каждом шаге берём меньшую из двух верхних карт и кладём её

(рубашкой вверх) в результирующую стопку.

38


4. Когда одна из оставшихся стопок становится пустой, мы добавляем все

оставшиеся карты второй стопки к результирующей стопке.

Рис.1. Сортировка слиянием

Время работы процедуры Merge_Sort𝐓(𝒏) в самом неблагоприятном случае

описывается с помощью следующего рекуррентного соотношения:

Разбиение.В ходе разбиения определяется, где находится середина

подмассива. Эта операция длится фиксированное время поэтому 𝑫(𝒏) =

𝚯(1) (рис. 2, а).

Покорение.Рекурсивно решаются две подзадачи, объем каждой из которых

составляет 𝑛/2. Время решения этих подзадач равно 2 ∙ 𝐓(𝒏/𝟐) (рис. 2, б).

Комбинирование. Процедура Merge в 𝑛 -элементном подмассиве

выполняется в течение времени 𝚯(𝒏), поэтому 𝑪(𝒏) = 𝚯(𝒏) (рис. 2, в).

39

Рис. 2. а, б, в – Методы разбиения, покорения и комбинирования

Асимптотическая функция временных трудозатрат алгоритма сортировки

слиянием (рис. 3):

Рис. 3.Асимптотическая функция временных трудозатрат алгоритма

40

𝟐 ∙ 𝒍𝒐𝒈𝟐 𝒏 = 𝒏.

Всего уровней(𝒍𝒐𝒈𝟐 𝒏 + 𝟏),𝑻(𝒏) = 𝒄𝒏(𝒍𝒐𝒈𝟐 𝒏 + 𝟏) = 𝐎(𝒏 ∙ 𝒍𝒐𝒈𝟐 𝒏)

Такой подход получил название построения дерева рекурсии.

Пример 2.T(n) = 3T(n/4) + c𝑛2 (рис. 4).

cn2

T(n/4) T(n/4) T(n/4)

cn2

c(n/4)2

c(n/4)2

c(n/4)2

T(n/16) T(n/16) T(n/16) T(n/16) T(n/16) T(n/16) T(n/16) T(n/16) T(n/16)

cn2

c(n/4)2

log 4 𝑛

с(n/16)2 с(n/16)2 с(n/16)2

𝑐𝑛2

c(n/4)2

с(n/16)2с(n/16)2с(n/16)2

c(n/4)2

с(n/16)2с(n/16)2 с(n/16)2

3

( ) 𝑐𝑛2

16

3 2 2

( ) 𝑐𝑛

16

T(1) T(1) T(1) T(1) T(1) T(1)

T(1) T(1) T(1)

…

T(1) T(1) T(1) T(1) T(1)

Θ(𝑛log4 3 )

Всего 𝐎(𝒏𝟐 )

Рис. 4. Построение дерева рекурсии

41


Теорема.Пусть 𝑎 > 1 и𝑏 > 1 – константы, 𝑓(𝑛) – произвольная функция, а

𝑇(𝑛) – функция, определенная на множестве неотрицательных целых чисел с

помощью рекуррентного соотношения (𝑛/𝑏 == [𝑛/𝑏])

𝒏

𝑻(𝒏) = 𝒂𝑻 ( ) + 𝒇(𝒏)

𝒃

Тогда асимптотическое поведение функции Т(n) можно выразить следующим

образом:

1.Если𝐹(𝑛) = Ο(𝑛𝑙𝑜𝑔𝑏 𝑎−𝜀 )для некоторой константыε > 0, то

𝑇(𝑛) = Θ(𝑛𝑙𝑜𝑔𝑏 𝑎 ).

2.Если𝐹(𝑛) = Θ(𝑛log𝑏 𝑎 ),то

𝑇(𝑛) = Θ(𝑛𝑙𝑜𝑔𝑏 𝑎 ∙ lg𝑛).

3.Если𝐹(𝑛) = Ω(𝑛𝑙𝑜𝑔𝑏 𝑎+𝜀 ) для некоторой константы ε > 0 и, если 𝑎𝑓(𝑛/𝑏) ≤

𝑐𝑓(𝑛) для некоторой константы 𝑐 < 1 и всех достаточно больших 𝑛, то

𝑇(𝑛) = Θ(𝑓(𝑛)).

Чтобы использовать основной метод, достаточно определить, какой из

частных случаев основной теоремы (если такой есть) применим в конкретной

задаче, а затем записать ответ.

Пример 3.

𝑇(𝑛) = 9𝑇(𝑛⁄3) + 𝑛, 𝑓(𝑛) = 𝑛, 𝑎 = 9, 𝑏 = 3.

𝑓 (𝑛) = 𝑛 = Ο(𝑛log𝑏 𝑎−ε ) = Ο(𝑛log3 9−1 ) = Ο(𝑛), то приходим к случаю 1.

𝑇(𝑛) = Θ(𝑛2 ).

Пример 4.

𝑓 (𝑛) = 1 = 𝑛

Пример 5.

log3⁄ 1

2

𝑇(𝑛) = 𝑇(2𝑛⁄3) + 1, 𝑓(𝑛) = 1, 𝑎 = 1, 𝑏 = 3⁄2.

= 𝑛0 , то приходим к случаю 2.

𝑇(𝑛) = Θ(log 2 𝑛).

𝑇(𝑛) = 3𝑇(𝑛⁄4) + 𝑛 ∙ lg𝑛.

𝑓 (𝑛) = 𝑛log4 3 .

𝑇(𝑛) = 𝑛0.972 log 2 𝑛 = Θ(𝑛 log 2 𝑛).

Более общий случай разбиения задачи на существенно неравные подзадачи:

𝑛

(𝑛) = ∑ 𝑎𝑖 𝑇 ( ) + 𝑓(𝑛)𝑇

𝑏𝑖

𝑖=1

𝑘

𝑇(𝑛) = Θ(𝑛

𝑝 )

𝑓(𝑥)

+ Θ (𝑛 ∫ 𝑝+1 𝑑𝑥 )

𝑥

𝑝

𝑛′

𝑛

42

𝒂𝒊 > 0, 𝒃𝒊 > 1, ∑

𝑘

𝑖=1

𝑎𝑖 𝑏𝑖

−𝑝

= 1.

Пример 6. Вычисление факториала (рис. 5).

Рис. 5. Прямая рекурсия

𝐹(0) = 1

𝐹(𝑛) = 𝑛 ∗ 𝑓(𝑛 − 1)

𝑇(𝑛) = 𝑇(𝑛 − 1) + Θ(1) = 𝑐𝑛

Пример 7. Наибольший общий делитель

FunctionGCD(A, B)

IfAModB = 0

GCD = B

Else

GCD = GCD(B, A Mod B)

' Нет. Рекурсия.

𝑇0 = 𝑇(𝑚𝑜𝑑) + 1 + 1 = 𝐹(𝑚𝑜𝑑) + 2 – трудоемкость до рекурсии

𝑇(𝑛) = 𝑇(𝑛 − 1) + 𝑇(𝑚𝑜𝑑) + 1 = 𝑛 [𝑇(𝑚𝑜𝑑) + 1] + 1 – трудоемкость при

достижении рекурсии.

Косвенная рекурсия(рекурсивная процедура вызывает другую процедуру,

которая, в свою очередь, вызывает первую) (рис. 6).

𝑇1(𝑛) = 𝑇2(𝑛 − 1) + Θ(1)

𝑇2(𝑛) = 𝑇1(𝑛 − 1) + Θ(1)

' Делится ли B на A нацело?

' Да. Процедура завершена.

Рис. 6. Косвенная рекурсия

Пример 8. Вычисление чисел Фибоначчи (рис. 7).

𝑭𝒊𝒃(𝒏) = 𝑭𝒊𝒃(𝒏 − 𝟏) + 𝑭𝒊𝒃(𝒏 − 𝟐)

43

Function Fib(n)

If n <= 1

Fib = 1

Else

Fib(n) = Fib(n - 1) + Fib(n - 2)

Рис. 7. Вычисление чисел Фибоначчи

Анализ времени выполнения программы

Сколько раз выполняется одно из условий остановки 𝑛 ≤ 1

G(0) = 1

G(1) = 1

G(n) = G(n - 1) + G(n - 2)

H(0) = 0

H(1) = 0

H(n) = 1 + H(n - 1) + H(n - 2) для n> 1.

Тогда 𝑯(𝒏) = 𝑭𝒊𝒃(𝒏) − 𝟏 и 𝑮(𝒏) = 𝑭𝒊𝒃(𝒏)

Окончательно: 𝑻(𝒏) = 𝑯(𝒏) + 𝑮(𝒏) = 𝟐𝑭𝒊𝒃(𝒏) − 𝟏.

Общее решение уравнения Фибоначчи имеет вид:

1 + √51 + √5

𝐹 (𝑛) = 𝐶1 () + 𝑐2 ()

22

𝑛

𝑛

для n> 1

Сколько раз алгоритм достигает рекурсивного шага

Начальными условиями являются значения 𝐹(0) = 0 и 𝐹(1) = 1 . В

соответствии с этим получаем систему уравнений

𝑐1 + 𝑐2 = 0,

{√5

(𝑐1 − 𝑐2 ) = 1.

2

44


Решая эту систему уравнений, находим:

1

𝑐1 = −𝑐2 =

√5

𝑛𝑛

1 1 + √51 − √5

(𝑛) =𝐹[() −() ]

22

√5

Опасности рекурсии:

1. Бесконечная рекурсия.

2. Потери памяти.

Существует несколько способов уменьшения этих накладных расходов:

• Не следует использовать большого количества ненужных переменных.

Даже если подпрограмма их не использует, но память под эти переменные

будет отводиться.

• Можно уменьшить использование стека за счет применения глобальных

переменных.

• При использовании статических переменных системе не нужно отводить

память под новые копии переменных при каждом вызове подпрограммы.

3. Необоснованное применение рекурсии.

Приведенные выше функции факториала, наибольшего общего делителя,

чисел Фибоначчи не обязательно должны быть рекурсивными.

Контрольные вопросы

1. С какой целью применяется система сравнительных оценок

алгоритмов?

2. Приведите общее определение трудоемкости алгоритма решения

задачи с учетом его комплексного анализа.

3. Приведите примеры количественно-зависимых по трудоемкости

алгоритмов.

4. Приведите примеры параметрически-зависимых по трудоемкости

алгоритмов.

5. Приведите примеры количественно-параметрических по

трудоемкости алгоритмов.

6. В чем заключается цель асимптотического анализа функций

трудоемкости алгоритмов?

7. Приведите примеры θ-оценок роста функций трудоемкости.

жүктеу/скачать 3,71 Mb.

Достарыңызбен бөлісу: