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

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

1) Емпіричний (експериментальний) – обчислення часу виконання шляхом запуску на виконання реалізації алгоритмів. Допущення:

1 категорія - реалізація

01. алгоритми реалізовані на тій же самій мові програмування;

02. реалізація алгоритмів виконується з однаковою ретельністю;

03. виконуваний код (програма) алгоритмів має бути отриманий з використанням одного і того ж середовища програмування;

04. виконання алгоритмів виконується на одній і тій самій машині.

2 категорія – вхідні дані

01. використання реальних даних (точне вимірювання часу виконання);

02. використання випадкових даних (гарантія аналізу самого алгоритму, вимірювання середнього часу виконання);

03. використання незвичайних даних (вимірювання найгіршого випадку).

Приклад емпіричного аналізу алгоритмів послідовного і бінарного пошуків:

- пошук виконується в масиві цілих значень (невпорядкована структура);

- розмірність масиву у діапазоні від до

- кількість операцій пошуку елемента у діапазоні від до ;

- набір даних і пошук елементів один і той самий;

- масив ініціалізується випадковими значеннями.

а) Невдалий послідовний пошук – у найгіршому і середньому випадках треба перевіряти усі N елементів; успішний - в середньому перевіряється N/2 елементів.

Послідовний пошук у впорядкованому масиві:

невдалий – N/2 елементів у середньому і N елементів у найгіршому випадку; вдалий пошук – N/2 елементів у середньому (час виконання пропорційний кількості елементів).

б) При використанні бінарного пошуку перевіряється не більше елементів:
N = 100 -> 50 -> 25 -> 12 -> 6 -> 3 -> 1.

2) Математичний (аналітичний) – обчислення відносного часу виконання шляхом побудови математичного виразу. Застосовується якщо:

1. відсутня реалізація алгоритму;

2. необхідно передбачити час виконання алгоритму у новому середовищі;

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

Залежність часу виконання можна виразити через головний параметр з використанням простих математичних формул, що називаються ріст функціями:

1. 1- постійний час виконання (майже всі операції виконуються один раз або декілька); наприклад – пошук індексуванням за ключем;

2. N- лінійний час виконання (якщо кожний елемент обробляється); наприклад – послідовний пошук;

3. logN- логарифмічний час виконання (задача розбивається на набір під-задач, із зменшенням розміру задачі на кожному кроці на деякий постійний коефіцієнт, і розв’язок визначається в одній із під-задач); наприклад – бінарний пошук.

4. NlogN- час виконання пропорційний NlogN (задача розбивається на під-задачі, розв’язки яких потім об’єднуються); наприклад, низхідне сортування злиттям;

5. - квадратичний час виконання (коли опрацьовуються усі пари елементів – подвійні цикли); наприклад, сортування алгоритмом вставки у найгіршому випадку;

6. - кубічний час виконання (потрійні цикли); наприклад, сортування двовимірного масиву за значеннями одного рядка алгоритмом бульбашки;

7. - експоненціальний час виконання (прямий розв’язок задачі); наприклад, розклад числа на прості множники (ряди).

Для побудови аналітичного виразу, яким обчислюється час виконання, треба визначити всі операції, їх кількість та час виконання, і отриманий вираз можна перетворити, виразивши його через ріст функції. Для приблизної оцінки часу виконання алгоритму при більших значеннях N можна спростити математичний вираз, відкинувши додатки «нижчих порядків». Оцінка порядку росту часу виконання алгоритму при великих об’ємах набору даних називається асимптотичною ефективністю. Її математичний запис називається «тета-нотацією» T(n)= (g(n)), де (g(n)) - множина функцій, для яких справедливе висловлювання:

f(n) is (g(n)), якщо існують константи c(1) c(2) і n(0), такі що 0<=c(1)g(n)<=f(n)<=c(2)g(n) для всіх n>=n(0).

Визначення асимптотичної верхньої межі – О-нотація;

f(n) is O(g(n)), якщо існують c і n(0), такі що 0<=f(n)<=cg(n) для всіх n>=n(0).

Нижньої межі – омега-нотація:

-||- 0<=cg(n)<=f(n) -||-.

Через О-нотацію описується найгірший випадок – наприклад, сортування за зростанням алгоритмом вставки масиву, який уже відсортовано за спаданням.
Через омегу описується найкращий випадок – наприклад, масив даних уже впорядковано.
Приклад розрахунку асимптотичної оцінки для алгоритму сортування вставкою:
N=m.length; c1 -> N; c2 -> N-1; c3; c4 -> sum(j=1 to N-1)k(j); c5 ->.. k(j)-1; c6; c7 -> N-1.
T(N)=уся оця байда додається))

01. найкращий випадок (масив відсортовано у потрібному порядку):

c1N; c2…c4, c7 … all*(N-1) = (c1…)N + (c2..c7)=aN+b;

02. найгірший випадок (масив відсортовано у оберненому порядку):

sum(j=1 to N-1)k(j)= sum(j=1 to N-1)j=(N*(N+1)/2)-1; ….

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