Лабораторна робота № 4
"Асимптотичні характеристики складність алгоритму.
Алгоритми з поліноміальною та експоненціальною складністю".
Мета роботи : Ознаьомлення з асимптотичними характеристиками складності та класами складності алгоритмів.
Зміст роботи:
I. Теоретична частина.
Основні поняття та визначення
Параметри алгоритму.
Характеристики алгоритму.
Асимптотична складність.
Алгоритми з експоненціальною та поліноміальною складністю.
II. Практична частина
Для заданих функцій часової складності L(n) визначити асимптотичні характеристики O(n).
Розташувати отримані функції в порядку зростання.
Скласти програму (Pascal , C), яка ілюструє експоненціальну складність одного з алгоритмів, асимптотична складність якого була визначена в п2.
III. Висновки.
_______________________________________________________________________________
Зауваження до виконання роботи.
В процесі рішення задачі вибір алгоритма викликає певні труднощі. Алгоритм повинен задовільняти вимогам, які суперечать одна одній:
= бути простим для розуміння, переводу в програмний код, відлягодження.
= ефективно використовцвати комп'ютерні ресурси і виконуватись швидко.
Якщо програма повинна виконуватись декілька разів, то перша вимога більш важлива. Вартість робочого часу програміста перевищує вартість машинного часу виконання програми, тому вартість програми оптимізується по вартості написання ( а не виконання) програми. Якщо задача вимагає значних обчислювальних витрат, то вартість виконання програми може перевищити вартість написання програми, особливо коли програма повинна виконуватись багаторазово. Але навіть в цій ситуації доцільно спочатку реалізувати простий алгоритм, і з'ясувати яким чином повинна себе поводити більш складна програма.
На час виконання програми впливають наступні чинники:
= ввід інформації в програму
= якість скомпільованого коду
= машинні інструкції, які використовуються для виконання програми
= часова складність алгоритму (ЧС)
Часова складність є функцією від вхідних даних. Для деяких задач ЧС залежить від самих вхідних даних (знаходження найбільшого спільного дільника двох чисел), для інших – від їх "розміру" (задачі сортування).
Коли ЧС є функцією від самих даних, її визначають як ЧС для найгіршого випадку, тобто як найбільшу кількість інструкцій програми серед всіх можливих вхідних даних для цього алгоритму.
Використовується також ЧС в середньому ( в статистичному сенсі ), як середня кількість інструкцій по всім можливим вхідним даним. На практиці ЧС в середньому важче визначити ніж ЧС для найгіршого випадку, черезте що це математично важка для розв'язання задача, та, крім того, іноді важко визначити, що означає "середні" вхідні дані.
Коли ЧС є функцією від кількості вхідних даних, аналізується швидкість зростання цієї функції.
Асимптотичні співвідношення
Для опису швидкості зростання функцій використовується О-символіка. Позначемо функцію яка виражає залежність часової складності від кількості вхідних даних (n) через L(n) Тоді, наприклад, коли говорять, що часова складність L(n) алгоритму має порядок(ступінь) зростання O(n2) (читається як "О велике від n в квадраті, або просто "о від n в квадраті", то вважається, що існують додатні константи c i n0 такі, що для всіх n, більших або рівних n0, виконується нерівність L(n)<=cn2.
Наприклад, функція L(n) = 3n3+2n2 має порядок зростання O(n3).
Нехай n0=0 і с = 5. Очевидно, що для всіх цілих n>=0 виконується нерівність 3n3+2n2 <= 5n3.
Коли кажуть, що L(n) має ступінь зростання O(f(n)) , то вважається, що f(n) є верхньою границею швидкості зростання L(n). Щоби вказати нижню границю швидкості зростання L(n) використовують позначення ?(g(n)) , що означає існування такої константи с , що для нескінченогї кількості значень n виконується нерівність L(n)>=c g(n).
Теоретичне визначення порядку зростання функції є складною математичною задачею.
На практиці визначення порядку зростання є задачею, що цілком вирішується за допомогою кількох базових принципів.
Правило сум.
Це правило використовується для послідовних програмних фрагментів з циклами та розгалуженнями.
Порядок зростання скінченої послідовності програмних фрагментів (без врахування констант) дорівнює порядку зростання фрагменту з найбільшою часовою складністю.
Якщо алгоритм складається з двох фрагментів, функції часових складностей яких L1(n) і L2(n) мають ступені зростання O(f(n)) і O(g(n)) відповідно, то алгоритм має ступінь зростання O(max(f(n),g(n))).
Правило добутків.
Правило добутків полягає в наступному. Якщо L1(n) і L2(n) мають ступені зростання O(f(n)) і O(g(n))
відповідно, то добуток L1(n) L2(n) має ступінь зростання O(f(n)g(n)) .Прикладом може бути фрагмент програми "цикл в циклі".
Приклад.
Задані функції часової складності L(n) для чотирьох алгоритмів
EMBED Equation.3 EMBED Equation.3 EMBED Equation.3 EMBED Equation.3
1. 2. 3. 4.
Використавши правило сум і правило добутків знайдемо O(n) :
EMBED Equation.3 EMBED Equation.3 EMBED Equation.3 EMBED Equation.3
Розташуємо функції Oi(n) у порядку зростання
EMBED Equation.3
EMBED Equation.3 EMBED Equation.3 EMBED Equation.3
EMBED Equation.3
Функція має найбільшу ступінь зростання.
EMBED Equation.3
Побудуємо графіки, для k = 3,4,5; n = (1,2,…,10)
Для спрощення виберемо відповідно до к наступні поліноми EMBED Equation.3 , EMBED Equation.3 та EMBED Equation.3
EMBED Equation.3 EMBED Equation.3 EMBED Equation.3 Побудуємо графіки :
; n = 1,2,…
Графіки показують, що існують такі значення n (n=10 для к=3, n=16 для к=4, n=23 для к=5), починаючи з яких значення порядку зростання часової складності біде більше значення відповідного поліному. Це ілюструє приналежність алгоритму до класу експоненціальних алгоритмів.
