8.5
Аналіз трудомісткості алгоритму обчислення факторіала
Для розглянутого вище рекурсивного алгоритму обчислення факторіала кількість вершин рекурсивного дерева одно, очевидно, n, при цьому передається і повертається по одному значенню (m = 1, k = 1), в припущенні про збереження чотирьох регістрів – r = 4, а на останньому рекурсивному виклику значення функції обчислюється безпосередньо – в результаті: fA (n) = n * 2 * (1 + 1 + 4 + 1) + (n-1) * (1 + 3) + 1 * 2 = 18 * n – 2
Відзначимо, що n – параметр алгоритму, а не кількість слів на вході.
75
Рис. 8.3. Механізм виклику процедури з використанням програмного стека
8.6
Питання для
самоконтролю
1) Поняття індукції і рекурсії.
2) Приклади рекурсивного завдання функцій.
3) Рекурсивна реалізація алгоритмів.
4) Трудомісткість механізму виклику функції в мові високого рівня.
5) Рекурсивне дерево, рекурсивні виклики і повернення.
6) Аналіз трудомісткості рекурсивного алгоритму обчислення факторіала.
76
9.
РЕКУРСИВНІ АЛГОРИТМИ І МЕТОДИ ЇХ
АНАЛІЗУ
9.1
Логарифмічні тотожності
При аналізі рекурсивних алгоритмів досить часто використовуються логарифмічні тотожності, далі передбачається, що, a> 0, b> 0, c> 0, основа логарифма не дорівнює одиниці:
b
logba
= a; e
lnx
= x; log
b
a
c
= c * log
b
a;log
b
a = 1/log
a
b
log
b
a = log
c
a / log
c
b
⇒ записі Q (ln (x))
Основа логарифма не суттєва, якщо віна більше одиниці, оскільки константа ховається в позначенні Q.
a
logb c
=c
logb a
Можна показати, що для будь-якого ξ > 0 ln(n )= о(n
ξ
),
при n
→
∞
.
9.2 Методи рішення рекурсивних співвідношень
В математиці розроблено ряд методів, за допомогою яких можна отримати явний вигляд функції, які задані у рекурсивному виді [1, 5] – метод
індукції, формальні степеневі ряди, метод ітерацій і т.д.
Розглянемо деякі з них:
а) Метод індукції
Метод полягає в тому, що б спочатку вгадати рішення, а потім довести його правильність за допомогою індукції.
Приклад:
ƒ(0)=1
ƒ(n+1)=2*f(n)
77
Припущення: ƒ(n)=2
n
Базис: якщо ƒ(n)=2
n
, тоді ƒ(0)=1, що виконано за визначенням.
Індукція: Нехай ƒ(n)=2
n
,
тоді для n+1 ⇒ ƒ(n+1)= 2 * 2
n
=2
n+1
Зауважимо, що базис суттєво впливає на рішення. Так, наприклад:
- якщо ƒ(0)=0, то ƒ(n)=0;
- якщоƒ(0)=1/7, то ƒ(n)=(1/7)*2
n
;
-
якщо ƒ(0)=1/64, то ƒ(n)=(2)
n-6
б) Метод ітерації (підстановки)
Суть методу полягає в послідовній підстановці – ітерації рекурсивного визначення, з наступним виявленням загальних закономірностей:
Нехай ƒ(n)=3*ƒ(n/4)+n, тоді:
ƒ(n)=n+3*ƒ(n/4)=n+3*[ n/4+3*ƒ(n/16) ]=n+3* [n/4+3{ n/16+3*ƒ(n/64) } ],
і розкриваючи дужки, отримуємо:
ƒ(n)=n+3*n/4+9*n/16+27*n/64+…+3
i
*n/4
i
Зупинка рекурсії відбудеться при (n/4
i
)
≤
1
⇒
i
≥
log
4
n
, в цьому випадку останній доданок не більше, ніж 3
log4 n
*
Θ
(1) = n
log4 3
*
Θ
(1).
ƒ(n) = n*
∑
(3/4)
k
+ n
log4 3
*
Θ
(1),
тобто
∑
(3/4)
k
= 4*n, то остаточно:
ƒ(n) = 4 * n + n
log4 3
*
Θ
(1) =
Θ
(n).
78
9.3 Рекурсивні алгоритми
Основний метод побудови рекурсивних алгоритмів – це метод декомпозиції. Ідея методу полягає в розкладі задачі на частини меншої розмірності, отримані рішення для кожної частини і об'єднання рішень.
В загальному вигляді, якщо відбувається розділення задачі на b підзадач, яке призводить до необхідності вирішення a підзадач розмірністю n/b, то загальний вигляд функції трудомісткості має вигляд [5]:
f
A
(n )= a * f
A
( n/b )+d(n)+U(n) (9.1), де:
d(n) – трудомісткість алгоритму розподілу задачі на підзадачі,
U(n) –
трудомісткість алгоритму об'єднання отриманих рішень.
Розглянемо, наприклад, відомий алгоритм сортування злиттям, що належить Дж. Фон Нейману [5]:
На кожному рекурсивному виклику переданий масив ділиться навпіл, що дає оцінку для d(n) = Q(1). Далі рекурсивно викликається сортування отриманих масивів половинній довжини (до тих пір, поки довжина масиву не стане рівною одиниці), і зливаються повернені відсортовані масиви за Q (n).
Тоді очікувана трудомісткість на сортування складе:
f
A
(n )= 2 * f
A
( n/2 )+
Θ
(1)+
Θ
(n)
Виникає задача про отримання оцінки складності функції трудомісткості, заданої у вигляді (9.1), для довільних значень a і b.
9.4 Основна теорема про рекурентних співвідношеннях
Наступна теорема належить Дж. Бентлі, Д. Хакену та Дж. Саксу (1980 г.), достатньо повний доказ цієї теореми наведено в [5].
Теорема.
Нехай a
≥
1, b > 1 – константи, g(n) – функція.
Нехай далі:
ƒ(n)=a*ƒ(n/b)+g(n), де n/b =
(n/b)
або
(n/b)
79
Тоді:
1) Якщо g(n) = O(n
logba-
ξ
),
ξ
>0, то ƒ(n)=
Θ
(n
logba
).
Приклад:ƒ(n) = 8ƒ(n/2)+n
2
, тоді ƒ(n) =
Θ
(n
3
)
2) Якщо g(n)=
Θ
(n
log6a
), то ƒ(n)=
Θ
(n
logba
*log n).
Приклад: f
A
(n)= 2 * f
A
( n/2 )+
Θ
(n)
, тоді ƒ(n) =
Θ
(n*log n)
3) Якщо g(n) =
Ω
(n
logba+e
), e > 0
, то ƒ(n) =
Θ
(g(n)).
Приклад:ƒ(n)=2*ƒ(n/2)+n
2
, маємо: n
logba
= n
1
,
і відповідно: ƒ(n) =
Θ
(n
2
)
Дана теорема є потужним засобом аналізу асимптотичної складності рекурсивних алгоритмів, на жаль, вона не дає можливості отримати повний вид функції трудомісткості.
9.5 Питання для самоконтролю
1) Аналіз рекурсивних співвідношень методом ітерацій.
2) Аналіз рекурсивних співвідношень методом підстановки
3) Загальний вигляд функції трудомісткості для методу декомпозиції.
4) Основна теорема про рекурентних співвідношеннях.
5) Приклади розв'язання рекурентних співвідношень на основі теореми
Дж. Бентлі, Д. Хакена та Дж. Сакса.
80
10. ПРЯМИЙ АНАЛІЗ РЕКУРСИВНОГО ДЕРЕВА
ВИКЛИКІВ
10.1 Алгоритм сортування злиттям
Розглянемо підхід до отримання функції трудомісткості рекурсивного алгоритму, який заснований на безпосередньому підрахунку вершин дерева рекурсивних викликів, на прикладі алгоритму сортування злиттям.
Рекурсивна процедура Merge Sort – MS отримує на вхід масив А і два
індекси p і q, що вказують на ту частину масиву, яка буде сортуватися при даному виклику.
Допоміжні масиви Bp і Bq використовуються для злиття відсортованих частин масиву.
MS(A, p ,q, Bp, Bq)
If p
≠
q
(перевірка останову рекурсії при p=q)
then
r
←
(p+q) div 2
MS(A, p, r, Bp,Bq) (
рекурсивний виклик для першої частини)
MS(A, r+1, q, Bp,Bq)
(рекурсивний виклик для другої частини)
Merge(A, p, r, q, Bp, Bq)
(злиття відсортованих частин)
Return (A)
10.2 Злиття відсортованих частин (Merge)
Розглянемо процедуру злиття відсортованих частин масиву А, що використовує додаткові масиви Bp і Bq, в кінець яких з метою зупинки руху
індексу поміщається максимальне значення. Алгоритм рекурсивного сортування працює так, що частини масиву А, які об'єднуються, знаходяться поруч один з одним, тому алгоритм злиття спочатку копіює відсортовані частини в проміжні масиви, а потім формує об'єднаний масив безпосередньо в масиві А.
Merge (A,p,r,q,Bp,Bq)
Кількість операцій в даному рядку
Max
←
A[r]
2
If Max
2
Max
←
A[q]
½*2
kp
←
r – p + 1
3
p1
←
p – 1
2
81
For i
←
1 to kp
(
копіювання першої частини) 1+ kp*3
Bp [ i ]
←
A[p1 + i ]
kp*(4)
Bp[ kp+1]
←
Max
3
kq
←
q – r
2
For i
←
1 to kq
(
копіювання другої частини) 1+ kq*3
Bq [ i ]
←
A[ r + i ]
kq*(4)
Bq [ kq+ 1]
←
Max
3
(
зауважимо, що m=kp + kq = q – p + 1 – довжина об’єднаного масиву)
pp
←
p
1
pq
←
r+1
2
For i
←
p to q (
злиття частин)
1+m*3
If Bp [ pp ] < Bq [ pq ]
m*3
Then
A[ i ]
←
Bp[ pp ]
½*m*3
pp
←
pp +1
½*m*2
Else
A [ i ]
←
Bq [ pq ]
½*m*3
pq
←
pq +1
½*m*2
Return(A)
End
На підставі зазначеної кількості операцій можна отримати трудомісткість процедури злиття відсортованих масивів в середньому:
F
merge
(m)=
=2+2+1+3+2+1+kp*7+3+2+1+kq*7+3+1+2+1+m*(3+3+3+2)=
= 11*m + 7*(kp+kq) + 23 = 18*m+23. (10.1)
10.3 Підрахунок вершин в дереві рекурсивних викликів
Алгоритм, що має на вході масив з n елементів, ділить його навпіл при першому виклику, тому розглянемо випадок, коли n = 2k, k = log
2
n.
В цьому випадку ми маємо повне дерево рекурсивних викликів глибиною k, що містить n листів, фрагмент дерева показаний на рис 10.1.
82
Рис 10.1. Фрагмент рекурсивного дерева при сортуванні злиттям
Позначимо кількість вершин дерева через V:
V = n + n/2+n/4+n/8+...+1 = n*(1+1/2+1/4+1/8+...+1)=2n – 1=2
k+1
– 1
З них всі внутрішні вершини породжують рекурсію, кількість таких вершин – Vr = n-1. Решта n вершин – це вершини, в яких розглядається тільки один елемент масиву, що призводить до зупинки рекурсії.
10.4 Аналіз трудомісткості алгоритму сортування злиттям
Таким чином, для n листів дерева виконується виклик процедури MS c обчисленням r + 1 раз, перевіркою умови p = q і поверненням в названу процедуру для злиття. Ці дії в сумі з урахуванням трудомісткості виклику дають:
F1(n) = n*2*(5+4+1) + n*2(If p=q
і r+1) = 22*n.
Для n-1 рекурсивних вершин виконується:
- перевірка довжини масиву, що передається,
- обчислюється середина масиву,
- рекурсивний виклик процедур MS,
83
- повернення.
Оскільки трудомісткість виклику враховується при вході до процедури, то отримуємо:
Fr(n) = (n-1)*2*(5+4+1) + (n-1)*(1+3+1) = 24*n – 24.
Процедура злиття відсортованих масивів буде викликана n-1 раз. При цьому трудомісткість складається з трудомісткості виклику і власної трудомісткості процедури Merge.
Трудомісткість виклику становитиме (для 6 параметрів і 4-х регістрів):
Fm
виклик
(n) = (n-1)*2*(6+4+1) = 22*n – 22.
Оскільки трудомісткість процедури злиття для масиву довжиною m становить 18 * m + 23 (10.1), і процедура викликається n-1 раз з довжинами масиву рівними n, n/2, n/4, ..., причому 2 рази з довжиною n/2, 4 рази з довжиною n/4, то сукупно маємо:
Fm
злиття
(n) = (n-1)*23 + 18*n + 2*18*(n/2) + 4*18*(n/4) + … + =
= {враховуючи, що таким чином обробляються k-1 рівнів}
= 18*n *(log
2
n – 1) + 23*(n-1) = 18*n* log
2
n + 5*n – 23.
Враховуючи всі компоненти функції трудомісткості, одержуємо кінцеву оцінку:
Fa(n) = F1(n) + Fr(n) + Fm
виклик
(n) + Fm
злиття
(n) =
= 22*n + 24*n – 24 + 22*n – 22 +18*n* log
2
n + 5*n – 23 =
= 18*n* log
2
n + 73*n – 69 (10.2)
Якщо кількість чисел на вході алгоритму не дорівнює ступеню двійки, то необхідно проводити більш глибокий аналіз, заснований на вивченні поведінки рекурсивного дерева, проте при будь-яких ситуаціях з даними оцінка головного порядку
Θ
( n* log
2
n) не зміниться [5].
84
10.5 Питання для самоконтролю
1) Рекурсивний алгоритм сортування злиттям.
2) Процедура злиття двох відсортованих масивів.
3) Оцінка трудомісткості процедури злиття.
4) Підрахунок вершин в дереві рекурсивних викликів для алгоритму сортування злиттям.
5) Аналіз алгоритму рекурсивної сортування методом прямого підрахунку вершин рекурсивного дерева.
85
11. ТЕОРІЯ І АЛГОРИТМИ МОДУЛЯРНОЇ
АРИФМЕТИКИ
11.1 Алгоритм зведення числа в цілу ступінь
Задача про швидке зведення числа на всю ступінь, тобто обчислення значення y = x n
для цілого n лежить в основі алгоритмічного забезпечення багатьох криптосистем [9], відзначимо, що в цьому аспекті застосування обчислення виробляються за mod k
. Представляє інтерес детальний аналіз швидкого алгоритму зведення в ступінь методом послідовного зведення в квадрат [6]. В цілях цього аналізу представляється доцільним введення трьох наступних спеціальних функцій:
1. Функція β(n)
Функція визначена для цілого додатного n, і β(n) є кількість бітів у двійковому поданні числа n. Відзначимо, що функція β (n) може бути представлена у вигляді:
β(n) =[log
2
(n)]+1=[log
2
(n+1)], де [х] – ціла частина х, n > 0.
2. Функція β
1
(n)
Функція визначена для цілого додатного n, і β
1
(n) є кількість «1» в двійковому поданні числа n. При цьому, функція β
1
(n) не є монотонно зростаючою функцією, наприклад, для всіх n = 2
k
β
1
(n) = 1. Графік функції для початкових значень n представлений на рис 11.1.
Рис 11.1. Значення функції для n=1,2,…9.
Враховуючи визначення β
1
(n) справедлива нерівність:
1 2 3 4 5 6 7 8 9 n
β
1
(n)
4 3
86
1
≤
β
1
(n)
≤
β(n) =[log
2
(n)]+1, т.е.β
1
(n) = O(log
2
(n))
Відзначимо, що функція β
1
(n) може бути рекурсивно задана наступним чином [4]:
β
1
(0)=0; β
1
(1) = 1;
β
1
(n) =
β
1
(2n) = β
1
(n);
β
1
(2n+1)
= β
1
(n) + 1.
3. Функція β
0
(n)
Функція визначена для цілого додатного n, і β
0
(n)
є кількість «0» в двійковому поданні числа n. Функція β
0
(n) не є монотонно зростаючою функцією. Для всіх
n =2
k
-1,
β
0
(n)=0
Для будь-якого n справедливо співвідношення
β(n) = β
0
(n) + β
1
(n).
Для подальшого аналізу представляє також інтерес визначення середнього значення функції β
1
(n)
для n = {0,1,…,N}, де N=2
k
-1 (
тобто двійкове подання числа N займає k розрядів), позначимо йогочерез βs (N).
Тоді
∑
=
β
+
=
β
N
0
m s
s
)
m
(
1
N
1
)
N
(
Оскільки кількість чисел, що мають L одиниць в K розрядах дорівнює кількості сполучень з L по K, то тоді:
1
K
-1
k
0
L
L
K
k
1
L
-1
L
-1
K
k
1
L
L
K
N
0
m
s
2
*
K
C
*
K
C
L
K
*
L
C
*
L
(m)
β
−
=
=
=
=
=
=
=
=
∑
∑
∑
∑
, оскільки N=2
k
-1,
то:
2
β(N)
2
1)
(N
log
2
K
1
1
2
2
*
K
(m)
β
1
N
1
(N)
β
2
K
1
k
N
0
m
s
s
=
+
=
=
+
−
=
+
=
−
=
∑
(11.1).
Ідея швидкого алгоритму розв'язання задачі про зведення в ступінь полягає у використанні двійкового розкладання числа n і обчислення відповідних ступенів шляхом повторного зведення в квадрат [5].