Аналіз алгоритмів
З Вікіпедії, безкоштовно encyclopedia
Аналіз алгоритмів — це процес визначення обчислювальної складності алгоритмів, тобто кількості часу, пам'яті чи інших ресурсів, необхідних для виконання алгоритмів. Як правило, це передбачає визначення функції, яка пов'язує розмір вхідних даних алгоритму з кількістю кроків виконання (його часовою складністю) або кількістю місця, що він використовує (його просторовою складністю). Алгоритм вважається ефективним, якщо значення цієї функції малі або зростають повільно у порівнянні зі збільшенням розміру вхідних даних. Різні входи однакової довжини можуть призводити до різної поведінки алгоритму, тому найкращі, найгірші та середні[en] описи цих випадків можуть мати практичний інтерес. Якщо не вказано інше, функція, що описує складність алгоритму, зазвичай є верхньою межею, тобто, визначає його складність для найгірших випадків вхідних даних.
Термін «аналіз алгоритмів» був введений Дональдом Кнутом.[1] Аналіз алгоритмів є важливою частиною більш загальної теорії обчислювальної складності, яка встановлює теоретичні оцінки ресурсів, необхідних будь-якому алгоритму, що вирішує задану обчислювальну задачу[en]. Ці оцінки надають дослідникам розумні припущення щодо напрямків пошуку ефективних алгоритмів.
У теоретичному аналізі алгоритмів їх часто оцінюють в асимптотично, тобто, оцінкою функції складності для довільно великих вхідних даних. Для цього використовуються нотації «О» великого, великих Омега і Тета. Наприклад, бінарний пошук виконується за кількість кроків, пропорційну логарифму довжини відсортованого списку, в якому ведеться пошук, або за O(log(n)), відоме як «логарифмічний час». Звичайно асимптотичні оцінки використовуються тому, що різні рішення однієї і тієї ж задачі можуть мати різну ефективність. Звичною є ситуація коли ефективність двох «розумних» реалізацій одного алгоритму можуть відрізнятися сталим множником, який називається прихованою сталою.
Точні (не асимптотичні) вимірювання ефективності можуть бути обчислені, але потребують деяких припущень стосовно реалізації алгоритму, відомі як модель обчислення. Модель обчислення може бути визначена в термінах абстрактного комп'ютера, такого як машина Тюрінга, також в ній визначається час виконання кожної операції або робиться припущення, що всі операції виконуються за однаковий час. Наприклад, якщо відсортований список, до якого застосовується бінарний пошук, має n елементів, а також вважаємо, що кожна операція зчитування елемента списку виконується за якусь сталу одиницю часу, тоді, для отримання результату потрібно максимум log2 n + 1 одиниць часу.