Аналіз складності алгоритмів

Методичні вказівки

До лабораторної роботи № 3

 

з дисципліни

" AЛГОРИТМИ ТА МЕТОДИ ОБЧИСЛЕНЬ"

 

для студентів напряму

6.050102 “Комп’ютерна інженерія”

 

 

 

 

Львів – 2010

Методичні вказівки до комплексу лабораторних робіт з дисципліни "AЛГОРИТМИ ТА МЕТОДИ ОБЧИСЛЕНЬ" для підготовки студентів напряму 6.050102 “Комп’ютерна інженерія” / Укл. Т.А.Лисак – Львів: Видавництво НУ “Львівська політехніка”, 2010 – 18 с.

 

 

Укладач: Матвейчук Т.А., ст. викладач каф.ЕОМ

 

Відповідальний

за випуск: Мельник А.О., д-р техн. наук, проф.

 

 

Рецензенти: Мороз І.В., ст. викладач каф.ЕОМ

 

Юрчак І.Ю., доцент кафедри САПР, к.т.н.

 

МЕТА РОБОТИ

Оволодіти методикою аналізу складності основних алгоритмічних конструкцій. Навчитись обчислювати функцію трудомісткості. Ознайомитись з класифікацією алгоритмів на основі функції трудомісткості. Опанувати методику аналізу розроблених алгоритмів на предмет їх складності.

ТЕОРЕТИЧНІ ВІДОМОСТІ

Складність алгоритмів

Для оцінки алгоритмів існує багато критеріїв. Найбільшу увагу приділяють порядку росту, необхідного для розв'язання задачі часу та розміру пам'яті при збільшені вхідних даних. З кожною конкретною задачею зв'язане число, яке називається розміром задачі і яке виражає міру кількості вхідних даних. Наприклад, розміром задачі множення матриць може бути найбільший розмір матриць-співмножників. Розміром задачі про графи може бути число ребер даного графа.

Час, затрачений на обчислення при виконанні алгоритму, являє собою суму часів окремих виконаних операторів. Програму, написану на мові високого рівня, можна перетворити прямим (хоча і не простим) шляхом в програму на машинному коді заданої ЕОМ. Це в принципі дає метод оцінки часу виконання вказаної програми, але такий підхід орієнтований на конкретну ЕОМ і не дає загальної залежності часу обчислення від розмірів задачі. В області аналізу та побудови алгоритмів прийнято виражати час виконання, як і будь-яку іншу міру ефективності, з точністю до мультиплікативної константи. Це, зазвичай, робиться шляхом підрахунку лише певних ключових операцій, виконаних алгоритмом (що легко здійснити, аналізуючи версію цього алгоритму, записану на мові високого рівня). Такий підхід абсолютно правомірний при визначені нижніх оцінок часу виконання, оскільки невраховані операції можуть лише збільшити їх; однак при роботі з верхніми оцінками ми повинні впевнитись у тому, що вклад вибраних ключових операцій в сумі відрізняється не більше, ніж в константу раз від вкладу всіх операцій, виконаних алгоритмом.

Час, який витрачається алгоритмом, як функція розміру задачі, називається часовою складністю цього алгоритму. T(n). Асимптотику поведінки цієї функції при збільшенні розміру задачі називають асимптотичною часовою складністю, а для її позначення використовують нотацію Ландау (велике O). Аналогічно, можна виділити просторову складність та асимптотичну просторову складність.

Саме асимптотична складність визначає розмір задач, які алгоритм здатен обробити. Наприклад, якщо алгоритм обробляє вхідні дані розміром n за час cn², де c - деяка стала, то кажуть, що часова складність такого алгоритму O(n²).

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

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

В основах аналізу алгоритмів до одного класу відносять всі функції, чий порядок росту однаковий з точністю до постійного множника. Ці класи, їх назви, а також деякі пояснення та приклади, наведені в таблиці 1 у відповідності до зростання їхнього порядку росту. Функції, які зростають повільніше, наведені першими. В таблиці прийнято, що n ∞, с - константа.

 

Таблиця 1. Основні асимптотичні класи ефективності

Часова складність	Назва класу	Коментар	Приклади
O(1)	Константний	Сталий час роботи не залежно від розміру задачі	Індексація масиву
O(log log n)	Log log n	Дуже повільне зростання необхідного часу	Очікуваний час роботи інтерполюючого пошуку n елементів
O(log n)	Логарифмічний	Логарифмічне зростання — под-воєння розміру задачі збільшує час роботи на сталу величину	Обчислення x^n, двійковий пошук в масиві з n елементів
O(n)	Лінійний	Лінійне зростання — подвоєння розміру задачі подвоїть і необхідний час	Додавання / віднімання чисел з n цифр; лінійний пошук в масиві з n елементів
O(n log n)	Лінеаритмічний (або n-log-n)	Лінеаритмічне зростання — подвоєння розміру задачі збільшить необхідний час трохи більше ніж вдвічі	Сортування злиттям, швидке сортування
O(n²)	Квадратичний	Квадратичне зростання — подвоєння розміру задачі вчетверо збільшує необхідний час	Прості методи сортування
O(n³)	Кубічний	Кубічне зростання — подвоєння розміру задачі збільшує необхідний час у вісім разів	Звичайне множення матриць
O(n^с)	Поліноміальний	Поліноміальне зростання — подвоєння розміру задачі збільшує необхідний час в 2^с раз	Задача комівояжера
O(c^n)	Експоненціальний	Експоненціальне зростання — збільшення розміру задачі на 1 призводить до c -кратного збіль-шення необхідного часу; подво-єння розміру задачі підносить необхідний час у квадрат	Алгоритми пошуку повним перебором
O(n!)	Факторіальний	Факторіальне зростання — збільшення розміру задачі на 1 збільшує необхідний час в n+1 раз	Обробка всіх перестано-вок деякої множини, що складається з nелементів

2.2. Функція трудомісткості і система позначень

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

Для порівняння ефективності алгоритмів при реальних розмірах входних даних і прогнозування часу виконання їхніх програмних реалізацій необхідне знання про точну кількість операцій досліджуваних алгоритмів, що характеризується функцією трудомісткості. Під трудомісткістю алгоритму для даної конкретної проблеми, що задається множиною D, розуміють кількість "елементарних" операцій, що задаються алгоритмом у прийнятій моделі обчислень. Відповідну функцію позначають як f_А(D). Значенням функції трудомісткості є ціле додатнє число.

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

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

У загальному випадку існує підмножина множини D_A, що містить всі конкретні проблеми, що мають розмірність n. Позначимо її через D_n:

Позначимо потужність множини D_n через М_Dn =|D_n|. Тоді алгоритм А, маючи на вході різні множини , буде, можливо, задавати в деякому випадку найбільшу, а в деякому випадку найменшу кількість операцій.

Введемо наступні позначення:

1. – найгірший випадок – найбільша кількість операцій, які необхідно виконати алгоритмом А для вирішення конкретної проблеми розмірністю n:

1. – найкращий випадок – найменша кількість операцій, які необхідно виконати алгоритмом А для вирішення конкретної проблеми розмірністю n:

1. – середній випадок – середня кількість операцій, які необхідно виконати алгоритмом А для вирішення конкретної проблеми розмірністю n:

.