Ім'я файлу: ТЕОРІЯ АЛГОРИТМІВ.pdf
Розширення: pdf
Розмір: 934кб.
Дата: 04.08.2022
скачати

38
Розглянемо більш докладно алгоритм пошуку максимуму в масиві S, що складається з n елементів:
MaxS (S,n; Max)
Max
←
S
1
For i
←
2 to n
if Max < S
i
then Max
←
S
i
(кількість виконаних операцій присвоювання залежить від порядку розташування елементів масиву).
4.4
Асимптотичний аналіз функцій
При аналізі поведінки функції трудомісткості алгоритму часто використовують прийняті в математиці асимптотичні позначення, що дозволяють показати швидкість росту функції, маскуючи при цьому конкретні коефіцієнти.
Така оцінка функції трудомісткості алгоритму називається складністю
алгоритму і дозволяє визначити переваги у використанні того чи іншого алгоритму для більших значень розмірності вхідних даних.
У асимптотичному аналізі прийняті наступні позначення [5]:
1. Оцінка
Θ
(тетта)
Нехай f (n) і g (n) – додатні функції додатного аргументу, n ≥ 1 (кількість об'єктів на вході і кількість операцій – додатні числа), тоді: f
g с
2
g(n)
f(n)
c
2
g(n),
f(n) =
Θ
(g(n)), якщо існують додатні с
1
, с
2
, n
0
, такі, що: с
1
* g(n)
≤
f(n)
≤
c
2
* g(n
), при n > n
0
.

39
Зазвичай кажуть, що при цьому функція g (n) є асимптотично точною оцінкою функції f (n), тому що, за визначенням, функція f (n) не відрізняється від функції g (n) з точністю до постійного множника.
Відзначимо, що з f (n) =
Θ
(g (n)) випливає наступне:
g (n) =
Θ
(f (n)).
Приклади:
1) f(n)=4n
2
+nlnN+174 – f(n)=
Θ
(n
2
);
2) f(n)=
Θ
(1) – запис означає, что f(n) або дорівнює константі, яка не дорівнює нулю, або f(n) обмежена константою на
∞
: f(n) = 7+1/n =
Θ
(1).
2. Оцінка О (О велике)
На відміну від оцінки
Θ
, оцінка О потребує тільки, що б функція f(n) не перевищувала g(n) починаючи з n > n0, з точністю до постійного множника:
∃
c > 0, n0 > 0 :
0
≤
f(n)
≤
c * g(n),
∀
n
>
n0
Взагалі, запис O(g(n)) означає клас функцій, які зростають не швидше, ніж функція g(n) з точністю до постійного множника. Тому іноді говорять, що g(n) мажорірує функцію f(n).
Наприклад, для всіх функцій:
f(n)=1/n,
f(n)= 12,
f(n)=3*n+17,
f(n)=n*Ln(n),
f(n)=6*n
2
+24*n+77
буде вірною оцінка О(n
2
).
Вказуючи оцінку О є сенс вказувати найбільш
«
близьку» функцію, оскільки, наприклад, для f (n) = n2 є справедливою оцінка О (2n), проте вона не має практичного сенсу.
n
0
f
,
g
n
c
2
g(n)
f(n)

40
3. Оцінка
Ω
(Омега)
На відміну від оцінки О, оцінка
Ω
є оцінкою знизу – тобто визначає клас функцій, які зростають не повільніше, ніж g(n) з точність до постійного множника:
∃
c > 0, n0 >0 :
0
≤
c * g(n)
≤
f(n)
Наприклад, запис Ω (n * Ln(n)) позначає клас функцій, які зростають не повільніше, ніж g (n) = n * Ln(n). В цей клас потрапляють всі поліноми зі ступенем більшої одиниці, так само як і всі степеневі функції з основою більш ніж одиниця.
Відзначимо, що не завжди для пари функцій справедливо одне з асимптотичних співвідношень, наприклад для f (n) = n1 + sin(n) і g(n) = n не виконується жодна з асимптотичних співвідношень.
У асимптотичному аналізі алгоритмів розроблені спеціальні методи отримання асимптотичних оцінок, особливо для класу рекурсивних алгоритмів.
Очевидно, що Θ є переважною оцінкою ніж оцінка О. Знання асимптотики поведінки функції трудомісткості алгоритму – його складності, дає можливість робити прогнози щодо вибору більш раціонального з точки зору трудомісткості алгоритму для великих розмірностей вхідних даних.
4.5
Питання для самоконтролю
1)
Формальна система мови високого рівня.
2)
Поняття трудомісткості алгоритму у формальному базисі.
3)
Узагальнений критерій оцінки якості алгоритму.
4) Система позначень в аналізі алгоритмів – найгірший, кращий і середній випадки.
5)
Класифікація алгоритмів по виду функції трудомісткості.
6)
Приклади кількісних і параметрично-залежних алгоритмів.
F(n)
cg(n)

41 7)
Позначення в асимптотичному аналізі функцій.
8)
Приклади функцій, не пов'язаних асимптотичними.

42
5. ТРУДОМІСТЬ АЛГОРИТМІВ ТА ЇХ ЧАСОВІ
ОЦІНКИ
5.1. Елементарні операції в мові запису алгоритмів
Для отримання функції трудомісткості алгоритму, представленого у формальній системі введеної абстрактної машини необхідно уточнити поняття «елементарних» операцій, співвіднесених з мовою високого рівня.
В якості таких «елементарних» операцій пропонується використовувати наступні:
1) Просте присвоювання: а ← b.
2) Одновимірна індексація a [i]: (адреса (a) + i * довжина елементу).
3) Арифметичні операції: (*, /, -, +).
4) Операції порівняння: a < b.
5) Логічні операції (l1) {or, and, not} (l2).
Спираючись на ідеї структурного програмування, виключимо команду переходу за адресою, вважаючи її пов'язаною з операцією порівняння в конструкції розгалуження.
Після введення елементарних операцій аналіз трудомісткості основних алгоритмічних конструкцій у загальному вигляді зводиться до наступних положень:
а) конструкція «Послідовного переходу»
Трудомісткість конструкції є сума трудомісткості блоків, які виконуються послідовно друг за другом.
F
«
Послідовного п
ереходу»
= f
1
+ … + f
k
,
де k – кількість блоків.

43
б) конструкція «Розгалуження»
if ( l ) then
f
then
з ймовірністю p
else
f
else
з ймовірністю (1-p)
Загальна трудомісткість конструкції «Розгалуження» вимагає аналізу ймовірності виконання переходів на блоки «Then» і «Else» і визначається як:
F
«
Розгалуження»
= f
then
* p + f
else
* (1-p).
в) конструкція «Цикл»
for i
←
1 to N
⇔
end
Після зведення конструкції до елементарних операцій її трудомісткість визначається як:
F
«цикл»
= 1+3*N+N*f
«тіло циклу»
5.2 Приклади аналізу простих алгоритмів
Приклад 1.
Задача підсумовування елементів квадратної матриці
SumM (A, n; Sum)
Sum
←
0
i
←
1
i
←
i+1
if i
≤
N

44
For i
←
1 to n
For j
←
1 to n
Sum
←
Sum + A[i,j]
end for
Return (Sum)
End
Алгоритм виконує однакову кількість операцій при фіксованому значенні n, отже є кількісно-залежним. Застосування методики аналізу конструкції
«Цикл» дає:
FA (n) = 1 +1 + n * (3 +1 + n * (3 +4)) = 7 n2 +4 * n +2 = Q (n2), зауважимо, що під n розуміється лінійна розмірність матриці, в той час як на вхід алгоритму подається n2 значень.
Приклад
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
Даний алгоритм є кількісно-параметричним, тому для фіксованої розмірності вхідних даних необхідно проводити аналіз для гіршого, кращого і середнього випадків.
а) найгірший випадок
Максимальна кількість переприсвоєння максимуму (на кожному проході циклу) буде в тому випадку, якщо елементи масиву відсортовані за зростанням. Трудомісткість алгоритму в цьому випадку дорівнює:

45
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 елементів загальна кількість операцій переприсвоєння максимуму визначається як:
0,57
γ
N
Ln
Hn
i
N
i
≈
+
≈
=
∑
=
,
)
(
/
1 1
γ
Величина Hn називається n-им гармонійним числом. Таким чином, точне значення (математичне очікування) середньої кількості операцій присвоювання в алгоритмі пошуку максимуму в масиві з n елементів визначається величиною Hn (на нескінченній кількості випробувань), тоді:
F
A
(n)=1 + (n-1) (3+2) + 2 (Ln(n) +
γ
) = 5 n +2 Ln(n) – 4 +2
γ
=
Θ
(n).
5.3
Перехід до часових оцінок
Порівняння двох алгоритмів за їх функцією трудомісткості вносить помилку в одержувані результати. Основною причиною цієї помилки є різна частотна елементарних операцій, що зустрічаються, породжувана різними

46 алгоритмами і відмінність в часах виконання елементарних операцій на реальному процесорі.
Таким чином, виникає задача переходу від функції трудомісткості до оцінки часу роботи алгоритму на конкретному процесорі:
Дано: F
A
(D
A
) – трудомісткість алгоритму. Потрібно визначити час роботи програмної реалізації алгоритму – T
A
(D
A
).
На шляху побудови часових оцінок стикаються з цілим набором різних проблем, пофакторний облік яких викликає суттєві труднощі.
Зазначимо основні з цих проблем:
• неадекватність формальної системи запису алгоритму і реальної системи команд процесора;
• наявність архітектурних особливостей процесора істотно впливають на час виконання програми, таких як конвеєр, кешування пам'яті, предвибірки команд і даних тощо;
• різні часи виконання реальних машинних команд;
• відмінність у часі виконання однієї команди, залежно від значень операндів;
• різні часи реального виконання однорідних команд в залежності від типів даних;
• неоднозначності компіляції вхідного тексту, зумовлені як компілятором, так і його налаштуванням.
Спроби різного підходу до обліку цих факторів призвели до появи різноманітних методик переходу до тимчасових оцінками.
1)
Поопераційний аналіз
Ідея поопераційного аналізу полягає в отриманні поопераційної функції трудомісткості для кожної з використовуваних алгоритмом елементарних операцій з урахуванням типів даних.
Наступним кроком є експериментальне визначення середнього часу виконання цієї елементарної операції на конкретній обчислювальній машині.
Очікуваний час виконання розраховується як сума добутків поопераційної трудомісткості на середні часи операцій:
T
A
(N) =
∑
F
А опер
(N) *

t
опер
,
де

t
опер
– час виконання елементарної операції.

47
2)
Метод Гіббсона
Метод передбачає проведення сукупного аналізу за трудомісткістю і перехід до часових оцінок з урахуванням належності розв'язуваної задачі до одного з наступних типів:
• задачі науково-технічного характеру, в яких переважно використовуються операції з операндами дійсного типу;
• задачі дискретної математики з переважанням операцій з операндами цілого типу;
• задачі баз даних з переважанням операцій з операндами рядкового типу.
Далі на основі аналізу великої кількості реальних програм для вирішення відповідних типів задач визначається частотна використання операцій (рис 5.1). Створюються відповідні тестові програми, і визначається середній час на операцію в даному типі задач –t
тип задачі
.
Рис 5.1. Можливий вид частоти використання операцій
На основі отриманої інформації оцінюється загальний час роботи алгоритму у виді:
T
A
(N) = F
A
(N) *

t
тип задачи
3) Метод прямого визначення середнього часу
У цьому методі так само проводиться сукупний аналіз за трудомісткістю
– визначається F
A
(N)
. Після цього на основі прямого експерименту для різних значень N
е визначається середній час роботи даної програми T
е
і за допомогою відомої функції трудомісткості розраховується середній час на
+
/
-
div
*
mod
P

48 узагальнену елементарну операцію, що породжується даним алгоритмом, компілятором і комп'ютером –

t
а
.
Ці дані можна (у припущенні про стійкість середнього часу по N)
інтерполювати або екстраполювати на інші значення розмірності задачі таким чином:

t
а
= T
э
(N
э
) / F
A
(N
А
), T(N) =

t
а
* F
A
(N).
5.4 Приклад поопераційного часового аналізу
У ряді випадків саме поопераційний аналіз дозволяє виявити особливі аспекти раціонального застосування того чи іншого алгоритму розв'язання задачі.
Як приклад розглянемо задачу множення двох комплексних чисел:
(a+bi)*(c+di)=(ac – bd) + i(ad + bc)=e + if
1.

1   2   3   4   5   6   7   8

скачати