Аналіз розроблюваних алгоритмів

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

1). Бути простим для розуміння, написання по ньому програми та подальшому її налагодженню.

2). Ефективно використовувати комп’ютерні ресурси і виконуватися по можливості швидко.

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

На час виконання програми впливають наступні фактори:

Ø введення початкової інформації в програму;

Ø якість скомпільованого коду виконуваної програми;

Ø машинні інструкції, що використовуються для виконання програми;

Ø складність програми – кількість інструкцій, що необхідно виконати для досягнення запланованого результату.

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

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

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

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

Таким чином, об'єктивним критерієм, що дозволяє оцінити ефективність того чи іншого алгоритму, є так званий порядок алгоритму. Порядком алгоритму називається функція O(N), що дозволяє оцінити залежність часу виконання алгоритму від обсягу перероблюваних даних (N – кількість елементів у масиві чи таблиці). Ефективність алгоритму тим вище, чим менше час його виконання залежить від обсягу даних. Більшість алгоритмів з погляду порядку зводиться до трьох основних типів:

Ø степенні – O(N^a);

Ø лінійні – O(N);

Ø логарифмічні – O(log_а(N)).

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

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

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

Ø Інколи ефективні алгоритми потребують занадто великих об’ємів машинної пам’яті, що зводить нанівець їх переваги.

Ø В обчислювальних алгоритмах точність та стійкість алгоритму не менш важливі, ніж їх ефективність за часом.