Поняття складності алгоритму та задачі

Використовуючи алгоритмічні моделі ми не замислювалися над обмеженням ресурсів. Але в реальних ЕОМ і пам’ять і час обмежені. Ось чому замало знати про існування того чи іншого алгоритму – необхідно мати уявлення про необхідні ресурси, а саме:

• чи може певна програма (алгоритм) розміститися в пам’яті ЕОМ;

• чи дасть вона результат за належний час.

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

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

Часова характеристика (фізичний час виконання) складності алгоритму –це величина τ*t, де t – кількість дій алгоритму (елементарних команд), а τ - середній час виконання однієї операції (команди).

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

Середній час τ - величина фізична і залежить від швидкості обробки сигналів в елементах і вузлах ЕОМ.

Ось чому об’єктивною математичною характеристикою складності алгоритму в певній моделі є кількість команд t.

Ємкісна характеристика складності алгоритмів визначається кількістю комірок пам’яті, що використовуються в процесі його обчислення. Ця величина не може перевищувати кількість дій t, що перемножена на певну константу (кількість комірок, які використовуються при виконанні однієї команди). В свою чергу, кількість дій t може перевищувати об’єм пам’яті (за рахунок використання повторень в одних і тих же комірках). До того ж проблема пам’яті технічно долається легше, аніж проблема швидкодії, яка має фізичне обмеження – швидкість розповсюдження фізичних сигналів (300 км/с). Ось чому часова складність вважається більш суттєвою характеристикою алгоритму.

Слід зазначити, що часова складність алгоритму не є постійною величиною і залежить від розмірності задачі (об’єм пам’яті для зберігання даних) – кількість комірок для різних даних.

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

Одиниця виміру T(n) точно не визначена, її розуміють як кількість кроків, що виконані на ідеалізованому комп’ютері.

У більшості випадків, при визначенні часової складності алгоритму Т(n), розуміють максимальний час виконання алгоритму по всім вхідним даним, так звану часову складність алгоритму Тmax(n) у найгіршому випадку.

Виконуючи аналіз алгоритмів використовують різні способи їх подання:

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

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

Почнемо з алгоритмів.

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

Нехай A позначає алгоритм розв'язання деякої масової задачі. Позначимо через F (A, екземпляр) кількість елементарних дій у процесі розв'язання цього екземпляра задачі за алгоритмом A, а через F (A, n) – максимум кількості елементарних дій серед усіх екземплярів розміру n.

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

F (A, n)=4× n× (n -1)/2.

Кожному n = 1, 2, 3, … відповідає певне значення F (A, n), тобто ми маємо функціональну залежність між розмірами n та максимальними кількостями елементарних дій, виконуваних за алгоритмом A. [http://emerecu.ukma.kiev.ua/books/PROG/ABU/abut7.htm]

Ця функція називається складністю алгоритму A. Алгоритми практично всіх реальних задач мають складність, монотонно неспадну за n.

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

Функція G (n) є оцінкою для функції F(n), або F(n) є функцією порядку G(n), коли існують такі додатні скінченні числа C ₁ і C ₂, що за деякого m при всіх n > m

C _1× G (n) £ F (n) £ C _2× G (n).

Така залежність між функціями позначається за допомогою знака "О":

F (n) = O(G (n)).

Для задання порядку зростання інколи користуються іншим означенням: функція F (n) називається функцією порядку G(n) за великих n, якщо , де C >0, C <¥.

Функція F (n) називається функцією порядку, меншого від G(n) за великих n, і це позначається F (n)=o(G (n)), якщо .

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

Виділяють такі основні класи алгоритмів:

* логарифмічні: f(n) = O (log2n);

* лінійні: f(n) = O (n);

* поліноміальні: f(n) = O (nm); тут m - натуральне число, більше від одиниці; при m = 1 алгоритм є лінійним;

* експоненційні: f(n) = O (an); a - натуральне число, більше від одиниці.

Приклад 1:. n× (n -1) = O(n ²), оскільки за n > 2 маємо 0.5× n ² < n *(n -1) < n ².

Аналогічно n ³ + 100× n ² = O(n ³) = o(n ^3.1) = o(2 ⁿ), 100× log n + 10000 = O(log n) = O(lg n) = o(n).

Приклад 2.

Складність алгоритму бульбашкового сортування tb (n)=O(n ²),

алгоритму лінійного пошуку – t ₁(n)=O(n),

бінарного пошуку – t ₂(n)=O(log n)

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

Тепер розглянемо поняття складності задачі.

Алгоритми пошуку в упорядкованому масиві свідчать, що одна й та сама задача може мати алгоритми розв'язання з різною складністю.

Неформально, під складністю задачі розуміють найменшу зі складностей алгоритмів її розв'язання. Іншими словами, з адача має складність порядку G(n), якщо існує алгоритм її розв'язання зі складністю O(G (n)) і не існує алгоритмів зі складністю o(G (n)).

Наприклад, складність задачі пошуку в упорядкованому масиві визначається складністю алгоритму двійкового пошуку, тому й оцінюється функцією log n. Задача сортування масиву має складність порядку n× log n. Доводити ці факти ми не будемо. (http://emerecu.ukma.kiev.ua/books/PROG/ABU/abut7.htm)

Поиск по сайту: