Файл: M51_21_-_kopia.pdf

36 

1.  F

a

∧

(N)  – 

найгірший  випадок  –  найбільша  кількість  операцій,  що 

здійснюються алгоритмом А для вирішення конкретних проблем розмірністю 
N:  

                F

a

∧

(N) = max {F

a

 (D)} – 

найгірший випадок на D

N 

2. F

a

∨

(N)  – 

кращий  випадок  –  найменша  кількість  операцій,  що 

здійснюються алгоритмом А для вирішення конкретних проблем розмірністю 
N: 

F

a

∨

(N) = min {F

a

 (D)} – 

кращий випадок на D

N 

3. F

a

(N)  – 

середній  випадок  –  середня    кількість  операцій,  що 

здійснюються алгоритмом А для вирішення конкретних проблем розмірністю 
N:                  

                F

a

(N) = (1 / M

DN

)*

∑

 {F

a

 (D)} – 

середній випадок на D

N

 
 
4.3  Класифікація алгоритмів по виду функції трудомісткості 
 

Залежно від впливу вхідних даних на функцію трудомісткості алгоритму 

запропонована  наступна  класифікація,  що  має  практичне  значення  для 
аналізу алгоритмів. 

1. 

Кількісно-залежні алгоритми за трудомісткістю 

 
Це  алгоритми,  функція  трудомісткості  яких  залежить  тільки  від 

розмірності конкретного входу, і не залежить від конкретних значень: 

 
F

a

 (D) = F

a

 (|D|) = F

a

 (N) 

 
Прикладами  алгоритмів  з  кількісно-залежною  функцією  трудомісткості 

можуть  служити  алгоритми  для  стандартних  операцій  з  масивами  і 
матрицями – множення матриць, множення матриці на вектор тощо. 

D

∈

D

N

D

∈

D

N

37 

2. 

Параметрично-залежні алгоритми за трудомісткістю. 

 
Це  алгоритми,  трудомісткість  яких  визначається  не  розмірністю  входу 

(як  правило,  для  цієї  групи  розмірність  входу  зазвичай  фіксована),  а 
конкретними значеннями оброблюваних слів пам'яті: 

F

a

 (D) = F

a

 (d

1

,…,d

n

) = F

a

 (P

1

,…,P

m

),  m 

≤

 n 

 
Прикладами  алгоритмів  з  параметрично-залежної  трудомісткістю  є 

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

а) Обчислення x

k

послідовним множенням  ⇒  F

a

(x, k) = F

a

 (k). 

б) Обчислення e

x 

= 

∑

 (x

n

/n!), 

з точністю до 

ξ

⇒ F

a

 = F

a

 (x, 

ξ

) 

3. 

Кількісно-параметричні за трудомісткістю алгоритми 

 
У  більшості  практичних  випадків  функція  трудомісткості  залежить  як 

від кількості даних на вході, так і від значень вхідних даних, в цьому випадку: 

F

a

 (D) = F

a

 ( ||D||, P

1

,…,P

m

) = F

a

 ( N, P

1

,…,P

m

) 

Як  приклад  можна  навести  алгоритми  чисельних  методів,  в  яких 

параметрично-залежний зовнішній цикл з точності включає в себе кількісно-
залежний фрагмент з розмірності.  

4. 

Порядково-залежні за трудомісткістю алгоритми  

 
Серед розмаїття параметрично-залежних алгоритмів виділимо групу, для 

якої кількість операцій залежить від порядку розташування вхідних об'єктів. 

Нехай множина D складається з елементів (d

1

,…,d

n

), 

і ||D||=N, 

Визначимо  D

p 

= {(d

1

,…,d

n

)}  – 

множину  всіх  впорядкованих  N-ок  з 

d

1

,…,d

n

, відмітимо, що |D

p

|=n!. 

Якщо F

a

 (

i

D

p

) 

≠

 F

a

 (

j

D

p

),  

де 

i

D

p

, 

j

D

p

∈

  D

p

, 

то  алгоритм  називають 

порядково-залежним за трудомісткістю.  

Прикладами  таких  алгоритмів  можуть  служити  ряд  алгоритмів 

сортування, алгоритми пошуку мінімуму і максимуму в масиві.  

38 

Розглянемо більш докладно алгоритм пошуку максимуму в масиві S, що 

складається  з n елементів: 

 
MaxS (S,n; Max) 

Max 

←

 S

1

For i

←

2 to n 

if Max < S

i

 then Max 

←

 S

i

(кількість  виконаних  операцій  присвоювання  залежить  від  порядку 
розташування елементів масиву). 

 
 
4.4 

Асимптотичний аналіз функцій  

При  аналізі  поведінки  функції  трудомісткості  алгоритму  часто 

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

Така  оцінка  функції  трудомісткості  алгоритму  називається  складністю 

алгоритму  і  дозволяє  визначити  переваги  у  використанні  того  чи  іншого 
алгоритму для більших значень розмірності вхідних даних. 

У асимптотичному аналізі прийняті наступні позначення [5]:  

1. Оцінка 

Θ

(тетта) 

Нехай  f (n) і g (n) – додатні функції додатного аргументу, n ≥ 1 (кількість 

об'єктів на вході і кількість операцій – додатні числа), тоді: 
 
       f

g

с

2

g(n) 

                            f(n)                        

                               c

2 

g(n),               

f(n) = 

Θ

 (g(n)), 

якщо існують додатні с

1

, с

2

, n

0

, такі, що: с

1 

* g(n) 

≤

 f(n) 

≤

c

2 

* g(n

), при n > n

0

 . 

39 

 
Зазвичай  кажуть,  що  при  цьому  функція  g  (n)  є  асимптотично  точною 

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

Відзначимо, що з f (n) = 

Θ

 (g (n)) 

випливає  наступне: 

                      g (n) = 

Θ

 (f (n)). 

Приклади: 

1) f(n)=4n

2

+nlnN+174 – f(n)= 

Θ

(n

2

); 

2)  f(n)=

Θ

(1)  – 

запис  означає,  что  f(n)  або  дорівнює  константі,  яка  не 

дорівнює нулю, або f(n) обмежена константою на 

∞

 : f(n) = 7+1/n = 

Θ

(1). 

2. Оцінка О (О велике) 

На відміну від оцінки 

Θ

, 

оцінка О потребує тільки, що б функція f(n) не 

перевищувала  g(n) починаючи з n > n0, з точністю до постійного множника: 

∃

 c > 0, n0 > 0 : 

0 

≤

 f(n) 

≤

 c * g(n), 

∀

n 

>

 n0 

Взагалі,  запис  O(g(n))  означає  клас  функцій,  які  зростають  не  швидше, 

ніж функція g(n) з точністю до постійного множника.  Тому  іноді говорять, 
що g(n) мажорірує функцію f(n).  

Наприклад, для всіх функцій: 
 
f(n)=1/n,  
f(n)= 12, 
 f(n)=3*n+17,  
f(n)=n*Ln(n),  
f(n)=6*n

2 

+24*n+77 

 
буде  вірною  оцінка  О(n

2 

). 

Вказуючи  оцінку  О  є  сенс  вказувати  найбільш 

«

близьку»  функцію,  оскільки,  наприклад,  для  f  (n) = n2  є  справедливою 

оцінка О (2n), проте вона не має практичного сенсу. 

n

0

f

,

g 

n 

c

2

g(n) 

f(n) 

40 

3. Оцінка 

Ω

(Омега) 

На  відміну  від  оцінки  О,  оцінка 

Ω

є  оцінкою  знизу  –  тобто  визначає 

клас функцій, які зростають не повільніше, ніж g(n) з точність до постійного 
множника: 

∃

 c > 0, n0 >0 :  

0 

≤

 c * g(n) 

≤

 f(n) 

 
 
Наприклад, запис Ω (n * Ln(n)) позначає клас функцій, які зростають  не 

повільніше,  ніж  g  (n)  =  n  *  Ln(n).  В  цей  клас  потрапляють  всі  поліноми  зі 
ступенем  більшої  одиниці,  так  само  як  і  всі  степеневі  функції  з  основою 
більш ніж  одиниця. 

Відзначимо,  що  не  завжди  для  пари  функцій  справедливо  одне  з 

асимптотичних співвідношень, наприклад для f (n) = n1 + sin(n) і g(n) = n не 
виконується жодна з асимптотичних співвідношень. 

У  асимптотичному  аналізі  алгоритмів  розроблені  спеціальні  методи 

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

Очевидно,  що  Θ  є  переважною  оцінкою  ніж  оцінка  О.  Знання 

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

 
 
4.5 

Питання для самоконтролю 

1)  

Формальна система мови високого рівня. 

2)  

Поняття трудомісткості алгоритму у формальному базисі. 

3)  

Узагальнений критерій оцінки якості алгоритму. 

4)  Система  позначень  в  аналізі  алгоритмів  –  найгірший,  кращий  і 

середній випадки.  

5)  

Класифікація алгоритмів по виду функції трудомісткості. 

6)  

Приклади кількісних і параметрично-залежних алгоритмів. 

F(n) 

cg(n)