на тему: Асимптотичні характеристики складності алгоритму. Алгоритми з поліноміальною та експоненціальною складністю.

абораторна робота №2

з дисципліни " Алгоритми та методи обчислень "

на тему: "Асимптотичні характеристики складності алгоритму. Алгоритми з поліноміальною та експоненціальною складністю".

 

 

Виконав:

студент групи КІ-22

Толочко О.В.

Прийняв:

старший викладач

Мітюков В.С.

 

 

Львів – 2012

Мета роботи: ознайомитись з асимптотичними характеристиками складності та класами складності алгоритмів.

 

 

Теоретична частина

В процесі розв’язку задачі вибір алгоритму викликає певні труднощі. Алгоритм повинен задовільняти вимогам, які часом суперечать одна одній:

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

= ефективно використовцвати комп'ютерні ресурси і виконуватись швидко.

 

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

 

На час виконання програми впливають наступні чинники:

= ввід інформації в програму

= якість скомпільованого коду

= машинні інструкції, які використовуються для виконання програми

= часова складність алгоритму (ЧС)

 

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

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

Використовується також ЧС в середньому (в статистичному сенсі), як середня кількість інструкцій по всім можливим вхідним даним. На практиці ЧС в середньому важче визначити ніж ЧС для найгіршого випадку, черезте що це математично важка для розв'язання задача, та, крім того, іноді важко визначити, що означає "середні" вхідні дані.

Коли ЧС є функцією від кількості вхідних даних, аналізується швидкість зростання цієї функції.

 

 

Практична частина

Використавши правило сум і правило добутків знайдемо O(n):

O₁(n) = n O₂(n) = O₃(n) = n⁶ O₄(n) = eⁿ

Розташуємо функції O_i(n) у порядку зростання

O₁(n) = n O₂(n) = O₃(n) = n⁶ O₄(n) = eⁿ

Функція O₄(n) = eⁿ має найбільшу степінь зростання.

 

 

Побудуємо графіки, для k = 3,4,5; n = (1,2,…,10)

Для спрощення виберемо відповідно до к наступні поліноми , та

Побудуємо графіки:

n = 1,2,…

 

 

К = 3

 

 

К = 4

 

К = 5

 

 

Висновок: Графіки показують, що існують такі значення n ₀(при зростанні к значення n ₀ теж зростає), починаючи з яких значення функції порядку зростання часової складності буде приймати більші значення ніж значення відповідного поліному. Це ілюструє приналежність алгоритму до класу алгоритмів з експоненціальною складністю.