ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 17.04.2019
Просмотров: 2335
Скачиваний: 1
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 <A[q] Then
2
Max
←
A[q]
½*2
kp
←
r – p + 1
3
p1
←
p – 1
2