НОУ ІНТУІТ, Лекція, Алгоритми обробки даних
Мета лекції: вивчити поняття та класифікації алгоритмів обробки даних, трудомісткості алгоритмів та методів її оцінки, навчитися виробленню критеріїв та оцінці трудомісткості алгоритмів з урахуванням критеріїв на прикладі реалізацій та завдань мовою C++.
Поняття"алгоритм обробки даних"у комп'ютерних науках використовується для опису методу вирішення задачі, який надалі можливо реалізувати у вибраному середовищі програмування. Ретельна розробка алгоритму є дуже ефективною частиною процесу розв'язання задачі у будь-якій галузі застосування. При розробці алгоритму для реальної задачі значні зусилля мають бути витрачені на усвідомлення ступеня її складності, з'ясування обмежень на вхідні дані, розбиття завдання на менш трудомісткі підзадачі.
Алгоритм не може бути прив'язаний до конкретної реалізації. У силу різноманітності використовуваних засобів програмування, їх вимог до апаратних ресурсів і платформної залежності подібні за структурою, але різні в реалізації, алгоритми можуть видавати результати, що відрізняються за ефективністю. При цьому деякі середовища програмування містять вбудовані бібліотечні функції, що реалізують базові алгоритми обробки даних (наприклад, у MS Visual Studio 2010 бібліотеки С++ входить функція швидкого сортування масивів даних). Щоб рішення були переносимими та залишалися актуальними, не рекомендується орієнтувати їх на процедурну реалізацію середовища. Тому головним у підході, що розглядається, є вибір методу рішення з урахуванням специфіки завдання. Адаптація до середовища здійснюється пізніше.
Вибір тієї чи іншої методу обробки даних визначається як складністю завдання. Враховувати необхідно і масовість застосування розробленого коду:одноразовому чи рідкісному зверненні до реалізації переважно бувають прості алгоритми, які нескладні розробки. Однак, допускається можливим збільшення часу роботи програми.
Масове використання алгоритмів обробки даних потребує пошуку найкращого алгоритму розв'язання. Такий процес дуже складний, оскільки вимагає вироблення критеріїв оцінки та застосування математичних методів для отримання кількісних характеристик. Напрямок комп'ютерних наук, що займається вивченням оцінки ефективності алгоритмів, називаєтьсяаналізом алгоритмів.
Ресурсна ефективність алгоритмів
Визначення ресурсної ефективності алгоритмів – необхідна складова етапу аналізу розробленого програмного забезпечення. Підвищення ресурсної ефективності обчислювальних алгоритмів є актуальним при обробці великих обсягів даних, коли апаратних та/або програмних ресурсів може бути недостатньо для коректного завершення роботи програмного коду.
Найбільш значущими характеристиками ресурсної ефективності алгоритмів є оцінки тимчасової та ємнісної складності, що відбивають ресурси процесора, оперативної пам'яті, а також зовнішніх носіїв даних (при використанні).
Підтрудомісткістю алгоритмуА на вході D будемо розуміти кількість елементарних операцій, які враховуються при аналізі алгоритму. Під найгіршим випадком трудомісткості розуміють найбільшу кількість операцій, що задаються алгоритмом А на всіх входах D певної розмірності n . Визначимо найкращий випадок трудомісткості, як найменша кількість операцій в аналогічному алгоритмі і при тій же розмірності входу.Середній випадоктрудомісткості визначається середньою кількістю операцій аналізованого алгоритму та вхідних даних. Залежністьтрудомісткості алгоритму А від значення параметрів на вході D визначає функцію трудомісткості алгоритму А для входу D .
Класичний аналіз алгоритмів у цьому контексті пов'язаний, перш за все, з оцінкою тимчасової складності. Більшість алгоритмів мають основний параметр, який значною мірою впливає на час виконання операцій. Якщо ж визначальних параметрів кілька, то, як правило, один із них виражається як функція від інших. Іноді використовують такий підхід: розглядають лише одне параметр , вважаючи інші константами.
Результатом аналізу єасимптотична оцінкавиконуваних алгоритмом операцій залежно від довжини входу, яка вказує порядок зростання функції та результати порівняння роботи алгоритмів для великих даних. При цьому оцінка на реальних даних відрізняється від асимптотичної тим, що вона орієнтована на конкретні довжини входів і число операцій, що виконуються алгоритмом.
Тимчасова складність алгоритмувизначається асимптотичною оцінкою функції трудомісткості алгоритму для гіршого випадку, позначається O(f(n)) і читається як "Про велике" або "О-нотація". Асимптотичний клас функцій включає в себе як середній, так і кращий випадок, тому що запис O(f(n)) позначає клас функцій, швидкість зростання яких не більше, ніж f(n) з точністю до деякої позитивної константи . Залежно від виду функції f(n) виділяють такі класи складності алгоритмів.
| 1 | Більшість інструкцій більшості функцій запускається один або кілька разів. Якщо всі інструкції програми мають таку властивість, то час виконання програмипостійно. |
| log N | Коли час виконання програми єлогарифмічним, програма стає повільніше зі зростанням N . Такий час виконання зазвичай притаманний програмам, які зводять велике завдання до набору менших підзадач, зменшуючи на кожному кроці розмір задачі на певний постійний фактор. Розглянемо час виконання, що є невеликою за величиною константою. Зміна підстави не сильно позначається на зміні значення логарифму: при N=1 000, log N = 3 якщо підстава дорівнює 10, або порядку 10, якщо підстава дорівнює 2; коли N=1 000 000 значення log N збільшується в два рази. При подвоєнні значення параметра log N зростає постійну величину, а подвоюється лише тоді, коли N досягає N 2 . |
| N | Коли час виконання програмилінійний, це зазвичай означає, що кожен вхідний елемент піддається невеликій обробці. Коли N дорівнює мільйону, так само і є час виконання. Коли N подвоюється, те відбувається і з часом виконання. Ця ситуація є оптимальною для алгоритму, який повинен обробити N вводів (або зробити N висновків). |
| N log N | Час виконання, пропорційне N log N виникає тоді, коли алгоритм вирішує завдання, розбиваючи її на менші підзавдання, вирішуючи їх незалежно і потім об'єднуючи рішення. Час виконання такого алгоритму дорівнює N log N. Коли N = 1000000 , . Коли N подвоюється, тоді час виконання більш ніж подвоюється. |
| N 2 | Коли час виконання алгоритму є квадратним , він корисний для практичного використання при вирішенні відносно невеликих завдань. Квадратичний час виконання зазвичай з'являється в алгоритмах, які обробляють усі пари елементів даних (можливо, у цикліподвійного рівня вкладеності). Коли N=1 000 час виконання дорівнює одному мільйону. Коли N подвоюється, час виконання збільшується вчетверо. |
| N 3 | Схожий алгоритм, який обробляє трійки елементів даних (можливо, у циклі потрійного рівня вкладеності), маєкубічнечас виконання і практично застосовується лише для малих завдань. Коли N=100 час виконання дорівнює одному мільйону. Коли N подвоюється, час виконання збільшується у вісім разів. |
| 2 N | Лише кілька алгоритмів з експоненційним часом виконання має практичне застосування, хоча такі алгоритми виникають природним чином при спробах прямого вирішення завдання, наприклад повного перебору. Коли N=20 час виконання має порядок одного мільйона. Коли N подвоюється, час виконання збільшується експонентно. |
На підставі математичних методів дослідження асимптотичних функцій трудомісткості на нескінченності виділено п'ять класів алгоритмів.
Клас 0- це клас швидких алгоритмів з постійним часом виконання, їх функція трудомісткості O(1). Проміжний стан займають алгоритми зі складністю O(log N), які також належать до даного класу.
Клас Р- це клас раціональних або поліноміальних алгоритмів, функція трудомісткості яких визначається поліноміально від вхідних параметрів. Наприклад, O(N), O(N 2 ), O(N 3 ) .
Клас L- це клас субекспоненційних алгоритмів зі ступенем трудомісткості O(N log N).
Клас E- це клас власне експоненційних алгоритмів зі ступенем трудомісткості O(2 N).
Клас F- це клас власне надекспоненційних алгоритмів. Існують алгоритми з факторіальною трудомісткістю, алевони переважно немає практичного застосування.
Стан пам'яті під час виконання алгоритму визначається значеннями, що вимагають розміщення певних ділянок. При цьому в ході вирішення завдання може бути задіяна додаткова кількість осередків. Підоб'ємом пам'яті, необхідним алгоритмом для входу D , розуміємо максимальну кількість осередків пам'яті, задіяних в ході виконання алгоритму.Ємнісна складність алгоритмувизначається як асимптотична оцінка функції обсягу пам'яті алгоритму для гіршого випадку.
Таким чином,ресурсна складність алгоритмуу гіршому, середньому та кращому випадках визначається як упорядкована пара класів функцій тимчасової та ємнісної складності, заданих асимптотичними позначеннями та відповідних даному випадку.