Архангельский А.Я. Программирование в Delphi. Учебник по классическим версиям Delphi. 2006 г. - 1152 с.

Додатково

10.4. Функція складності алгоритму

Для вирішення багатьох проблем існує безліч різних алгоритмів. Який з них вибрати для вирішення конкретного завдання? Це питання дуже ретельно опрацьовується в програмуванні. Ефективність програми є дуже важливою її характеристикою. Ефективність програми має дві складові: пам'ять (або простір) і час. Просторова ефективність вимірюється кількістю пам'яті, потрібної для виконання програми. Комп'ютери володіють обмеженим об'ємом пам'яті. Якщо дві програми реалізують ідентичні функції, то та, яка використовує менший об'єм пам'яті, характеризується більшою просторовою ефективністю. Іноді пам'ять стає домінуючим чинником в оцінці ефективності програм. Проте останніми роками у зв'язку з швидким її здешевленням ця складова ефективності поступово втрачає своє значення. Тимчасова ефективність програми визначається часом, необхідним для її виконання. Кращий спосіб порівняння эффективностей алгоритмів полягає в зіставленні їх порядків складності. Цей метод застосовний як до тимчасової, так і просторовій складності. Порядок складності алгоритму виражає його ефективність зазвичай через кількість оброблюваних даних. Наприклад, деякий алгоритм може істотно залежати від розміру оброблюваного масиву. Якщо, скажімо, час обробки подвоюється з подвоєнням розміру масиву, то порядок тимчасової складності алгоритму визначається як розмір масиву. Порядок алгоритму — це функція, домінуюча над точним виразом тимчасовій складності. Функція f(n)має порядок 0(g(n)),якщо є константа Kі лічильник n₀такі, що f(n)(K*g(n))для n>n₀. Наприклад: відомо, що точний час обробки масиву визначається з рівняння:

Дійсний час (довжина масиву)=

= Довжина масиву² + 5*Длина масиву + 100.

Грубе значення визначається допоміжною функцією:

Оцінка часу (довжина масиву)= 1,1*Довжина масиву² .

Функція складності Oвиражає відносну швидкість алгоритму залежно від деякої змінної (або змінних). Існують три важливих правила для визначення функції складності:

1. O(к*f)= O(f).

2. O(f*g) = O(f)*O(g) або O(f/g)= O(f) /O(g).

3. O(f+g)рівна домінанті O(f) і O(g). Тут до позначає константу, f і g — функції.

Перше правило декларує, що постійні множники не мають значення для визначення порядку складності

O(1,5*N)=O(N).

З другого правила виходить, що порядок складності множення двох функцій дорівнює множенню їх складнощів

O((17*N)*N)= O(17*N)*O(N) = O(N)*O(N) = O(N*N)= O(N²).

З третього правила виходить, що порядок складності суми функцій визначається як порядок домінанти першого і другого доданків, тобто вибирається найбільший порядок

O(N⁵ + N²) = O(N⁵).

10.4.1. Види функції складності алгоритмів

O(1)

У алгоритмах константної складності більшість операцій в програмі виконуються один або кілька разів. Будь-який алгоритм, що завжди вимагає незалежно від розміру даних одного і того ж часу, має константну складність.

O(N)

Час роботи програми лінійний, зазвичай коли кожен елемент вхідних даних потрібно обробити лише лінійне число разів.

O(N²), O(N³), O(N^a)

Поліноміальна складність. O(N²)— квадратична складність, O(N³)— кубічна складність

O(Log(N))

Коли час роботи програми логарифмічний, програма починає працювати набагато повільніше із збільшенням N. Такий час роботи зустрічається зазвичай в програмах, які ділять велику проблему на маленьких і вирішують їх окремо.

O(N*log(N))

Такий час роботи мають ті алгоритми, які ділять велику проблему на маленькі, а потім, вирішивши їх, об’єднують їх рішення.

O(2^N)

Експоненціальна складність. Такі алгоритми найчастіше виникають в результаті підходу, що називаються - “методом грубої сили”.

10.4.2. Часова функція складності

Програміст повинен уміти проводити аналіз алгоритмів і визначати їх складність. Тимчасова складність алгоритму може бути підрахована виходячи з аналізу його структур, що управляють.

Вид структури, що управляє Складність

Привласнення ... O( 1)

Простий вираз ... O(1)

S1; ... Домінанта для O(Обчис1) і

S2 ... O(Обчис2)

IF Умова THEN ... Домінанта для

S1 O(Обчис1) і О(Обчис2) і

ELSE О(ОбчисУмов)

S2 (* це якнайгірший випадок *)

FOR I:=l ТЕ N DO ... O( N * Обчис1)

S1

END

Зауваження. О(Обчис1), О(Обчис2) і О(ОбчисУмов) позначають відповідно складність обчислення для SI, S2 і для Умова.

Алгоритми без циклів і рекурсивних викликів мають константну складність. Якщо немає рекурсії і циклів, всі структури, що управляють, можуть бути зведені до структур константної складності. Отже, і весь алгоритм також характеризується константною складністю. Визначення складності алгоритму в основному зводиться до аналізу циклів і рекурсивних

викликів. Наприклад, розглянемо алгоритм обробки елементів масиву.

For i:=1 to N do

Begin

...

End;

Складність цього алгоритму O(N), оскільки тіло циклу виконується N разів, і складність тіла циклу рівна O(1). Якщо один цикл вкладений в інший і обидва цикли залежать від розміру однієї і тієї ж змінної, то вся конструкція характеризується квадратичною складністю.

For i:=1 to N do

For j:=1 to N do

Begin

...

End;

Складність цієї програми — O(N²).

10.4.3. Аналіз функції складності за програмою

Оцінимо складність програми «Трійки Піфагора»(мал. 1.26). Існують два способи аналізу складності алгоритму: висхідний (від внутрішніх структур, що управляють, до зовнішніх) і низхідний (від зовнішніх до внутрішніх).

0(H)= 0(1)+ 0(1)+0(1)=0(1);

0(I)= 0(N)*(0(F)+ 0(J)) = 0(N)*0 (домінанти умови) = 0(N);

0(G) = 0(N)*(0(C) + 0(I)+ 0(K)) = 0(N)*(0(l)+ 0(N) + + 0(1)) = 0(N²);

0(E) = 0(N)*(0(B) + 0(G) + 0(L)) = 0(N)*0(N²) = 0(N³);

0(D)= 0(A)+ 0(E)= 0(1)+ 0(N³)= 0(N³)

Таким чином, складність даного алгоритму — 0(N³).

Як правило, близько 90% часу роботи програми вимагає виконання повторень і лише 10% складають безпосередньо

Writeln('Bвести обмеження');

A Readln(N);

small:=l;

While small < N do

begin

B {next:=small;

While next <= N do

Begin

C { last:=next;

While last<=N do

Begin

D if (last<=small*2) and (next<=small*2) and

(last*last=small*small-next*next) then

E G begin

I F writeln(small);

H writeln(next);

writeln(last);

end;

J { inc(last);

end;

k { inc(next);

end;

L { inc(small);

end;

Мал. 1.26. Програма «Трійки Піфагора»

обчислення. Аналіз складності програм показує, на які фрагменти випадають ці 90 % — це цикли найбільшої глибини вкладеності. Повторення можуть бути організовані у вигляді вкладених циклів або вкладеної рекурсії. Ця інформація може використовуватися програмістом для побудови ефективнішої програми таким чином. Перш за все можна спробувати скоротити глибину вкладеності повторень. Потім слід розглянути можливість скорочення кількості операторів в циклах з найбільшою глибиною вкладеності. Якщо 90 % часу виконання складає виконання внутрішніх циклів, то 30 %-ве скорочення цих невеликих секцій приводить до 27 %-ому зниженню часу виконання всієї програми.

10.4.4. Оцінка алгоритму бінарного пошуку

Проведемо оцінку алгоритму бінарного пошуку в масиві.

function search(low, high, key: integer): integer; var

mid, data: integer;

Begin

while low<=high do

Begin

mid:=(low+high) div 2;

data:=a[mid];

if key=data then

search:=mid

Else

if key < data then

high:=mid-1

Else

low:=mid+1;

End;

search:=-1;

End;

Перша ітерація циклу має справу зі всім списком. Кожна подальша ітерація ділить навпіл розмір масиву. Так, розмірами списку для алгоритму є

n n/2¹ n/2² n/2³ n/2⁴ ... n/2ⁿ.

Врешті-решт буде таке ціле n, що

n/2^m<2 або n< 2^{m + 1}

Оскільки n — це перше ціле, для якого n/2^m<2, то повинно бути вірно

n/2^m-1>=2 або 2^m<=n.

З цього виходить, що

2^m<=n<2^{m + 1.}

Візьмемо логарифм кожної частини нерівності і отримаємо

m<= log₂n < m + 1.

Звідси, O(log₂n).

10.5.5. Теоретична і практична функції складності

Функція f(n)у ряді випадків може мати достатньо складну (навіть громіздку) аналітичну форму. Оскільки для тимчасової теоретичної складності більше значення має не стільки вид функції, скільки порядок її зростання, то в багатьох математичних дисциплінах, у тому числі і в теорії алгоритмів, функцию f(n) визначають як O(g(n)) і кажуть, що вона порядку g(n) для великих n, якщо

lim ^f(n)/_g(n)= const ≠ 0

де f(n)і g(n)— експериментальна і теоретична функції складності.

Приклад. Визначити функцію складності алгоритму за наслідками експерименту:

N	Кількість порівнянь

де N— кількість початкових даних в алгоритмі.

Рішення. Спочатку знайдемо експериментальну функцію складності (О_е). Експериментальна функція складності алгоритму приймає наступний ряд значень:

an an log₂n an² an³ аеⁿ an!

---------------------------------------------------------- >

Експериментальна функція

а) допустимий О_е = an, тоді

an = 54;

6а = 54;

a=54/6— (не задовольняє умові 1 <= а <= 2).

При а = 1 значення експериментальної функції співпадає із значенням теоретичної функції складності;

б) допустимий О_е = an log₂ n, тоді

an log₂ n= 54;

аn log₂ 6= 54;

54 9
а =------ =------ (а > 2 — не задовольняє умові);

6log₂ 6 log₂ 6

в) допустимий О_е = an², тоді

an² = 54;

а36= 54;

а = ------- = 1,5(а < 2— задовольняє умові).

Таким чином, експериментальна функція складності має вид O_e(1,5n²).

Знайдемо теоретичну функцію складності

lim O_e(n) /O_m(n) = const ≠ 0;

lim 1.5n²/X = const ≠ 0;

lim 1.5n²/n² = const ≠ 0;

Звідси, теоретична функція складності — 0(n²).

Питання:

1. Дати визначення основним лінгвістичним задачам.

2. Які є основні операції над стрічками.

3. Логічна структура стрічок.

4. Види функцій складності алгоритма.

5. Часова функція складності.

6. Аналіз функції складності за програмою.

7. Оцінка алгоритму бінарного пошуку.

8. Теоретична і практична функції складності

Література:

Архангельский А.Я. Программирование в Delphi. Учебник по классическим версиям Delphi. 2006 г. - 1152 с.

2. Архангельский А.Я. Delphi 2006. Справочное пособие: язык Delphi, классы, функции Win32 и .NET, 2006 г. - 1152 с.