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

абораторна робота №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₀ теж зростає ),починаючи з яких значення функції порядку зростання часової складності буде приймати більші значення ніж значення відповідного поліному. Це ілюструє приналежність алгоритму до класу алгоритмів з експоненціальною складністю .