Лекція "Оцінка складності алгоритмів, класифікація алгоритмів за складністю."

Лекція № 8

Тема: . Оцінка складності алгоритмів, класифікація алгоритмів за складністю.

Мета: Ознайомится сортуванням інших структур даних.

План

1. Поняття складності алгоритму.
2. Ефективність алгоритмів

Навчально-методичне забезпечення, ТЗН: конспект лекцій.

Література:

1. [2] стор. 300-305.
2. [3] стор. 89-102.

ВИКЛАД ЛЕКЦІЙНОГО МАТЕРІАЛУ

1.Поняття складносты алгоритму

У процесі вирішення прикладних задач вибір потрібного алгоритму викликає певні труднощі. І справді, на чому базувати свій вибір, якщо алгоритм повинен задовольняти наступні протиріччя.

1.                   Бути простим для розуміння, перекладу в програмний код і наладки.
2.                   Ефективно використовувати комп’ютерні ресурси і виконуватися швидко.

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

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

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

Більшість алгоритмів надає вибір між швидкістю виконання і ресурсами. Задача може виконуватися швидше, використовуючи більше пам’яті, або навпаки – повільніше з меншим обсягом пам’яті.

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

Із цього зв’язку випливає ідея просторово-часової складності алгоритмів. При цьому підході складність алгоритму оцінюється в термінах часу і простору, і знаходиться компроміс між ними.

При порівнянні різних алгоритмів важливо розуміти, як складність алгоритму співвідноситься із складністю вирішуваної задачі. При розрахунках за одним алгоритмом сортування тисячі чисел може зайняти 1 секунду, а сортування мільйона – 10 секунд, тоді як розрахунки за іншими алгоритмами можуть зайняти 2 і 5 секунд відповідно. У цьому випадку не можна однозначно сказати, яка із двох програм краща – це буде залежати від вихідних даних.

2. Ефективність алгоритмів

Одним із способів визначення часової ефективності алгоритмів полягає в наступному: на основі даного алгоритму потрібно написати програму і виміряти час її виконання на певному комп’ютері для вибраної множини вхідних даних. Хоча такий спосіб популярний і, безумовно, корисний, він породжує певні проблеми. Визначений час виконання програми залежить не тільки від використаного алгоритму, але й від архітектури і набору внутрішніх команд даного комп’ютера, від якості компілятора, і від рівня програміста, який реалізував даний алгоритм. Час виконання також може суттєво залежати від вибраної множини тестових вхідних даних. Ця залежність стає очевидною при реалізації одного й того ж алгоритму з використанням різних комп’ютерів, різних компіляторів, при залучені програмістів різного рівня і при використанні різних тестових даних. Щоб підвищити об’єктивність оцінки алгоритмів, учені, які працюють в галузі комп’ютерних наук, прийняли асимптотичну часову складність як основну міру ефективності виконання алгоритму.

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

Для багатьох програм час виконання дійсно є функцією вхідних даних, а не їх розміру. У цьому випадку визначають T(N) як час виконання в найгіршому випадку, тобто, як максимум часів виконання за всіма вхідними даними розміру N. Поряд з тим розглядають T_ср(N) як середній (в статистичному розумінні) час виконання за всіма вхідними даними розміру N. Хоча T_ср(N) є достатньо об’єктивною мірою виконання, але часто неможливо передбачити, або обґрунтувати, рівнозначність усіх вхідних даних. На практиці середній час виконання знайти складніше, ніж найгірший час виконання, так як математично це зробити важко і, крім цього, часто не буває простого визначення поняття „середніх” вхідних даних. Тому, в основному, користуються найгіршим часом виконання як міра часової складності алгоритмів.

Продуктивність алгоритму оцінюють за порядком величини. Говорять, що алгоритм має складність порядку , якщо час виконання алгоритму росте пропорційно функції із збільшенням розмірності початкових даних . – позначає „величина порядку”.

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

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

У числових алгоритмах точність і стійкість алгоритмів не менш важлива, ніж їх часова ефективність.

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

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

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

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

Час виконання операторів присвоєння, читання і запису звичайно має порядок .

Час виконання послідовності операторів визначається за правилом сум. Тому міра росту часу виконання послідовності операторів без визначення констант пропорційності співпадає з найбільшим часом виконання оператора в даній послідовності.

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

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

Контрольні запитання

1. Дайте визначення складності алгоритму.
2. Дайте визначення ефективності алгоритму.
3. Дайте визначення оцінці алгоритму.
4. Назвіть якості алгоритму.