ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 17.04.2019
Просмотров: 2331
Скачиваний: 1
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