ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 17.04.2019
Просмотров: 2346
Скачиваний: 1
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
Перехід до часових оцінок
Порівняння двох алгоритмів за їх функцією трудомісткості вносить
помилку в одержувані результати. Основною причиною цієї помилки є різна
частотна елементарних операцій, що зустрічаються, породжувана різними