Класифікація алгоритмів на основі функції трудомісткості

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

Виділимо в функції f_A(D) кількісну складову (залежну від n) і параметричну складову (залежну від значень і порядку слідування елементів в D), позначивши їх через f_n(n) та g_p(D)відповідно:

f_А(D) = f_А(f_n(n),g_p(D)).

Для більшості алгоритмів ця залежність може бути представлена як композиція функцій f_n(n) та g_p(D)або в мультиплікативній формі:

f_А(D) = f_n(n) · (D),

або в адитивній формі:

f_А(D) = f_n(n) + (D).

Введемо наступні позначення:

,

В залежності від впливу різних характеристик множини вхідних даних на функцію трудомісткості алгоритму, може бути запропонована наступна класифікація алгоритмів:

1. КласN (Numerical)– клас кількісно залежних по трудомісткості алгоритмів. Це алгоритми, функція трудомісткості яких, залежить тільки від розмірності вхідних даних

g⁺(n)=0, g^*(n)=1 => f_А(D) = f_n(n)

Прикладами алгоритмів з кількісно-залежною функцією трудомісткості можуть слугувати алгоритми для стандартних операцій роботи з масивами і матрицями, наприклад, множення матриць, множення матриці на вектор і т.д. Аналіз таких алгоритмів, як правило, не викликає труднощів. Зауважимо, що для алгоритмів класу N справедливе співвідношення

2. КласPR (Рarametritic) – клас параметрично залежних по трудомісткості алгоритмів. Це алгоритми, трудомісткість яких визначається не розмірністю входу (як правило, для цього класу розмірність входу фіксована), а конкретними значеннями всіх або деяких елементів із вхідної множини D:

f_n(n)=const = с => f_А(D) = c · (D)

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

- обчислення значення x^k методом послідовного множення, f_А(D) = f_А(x,k);

- обчислення значення експоненти із заданою точністю ε:

3. КласNPR – клас кількісно-параметрично залежних по трудомісткості алгоритмів. Це досить широкий клас алгоритмів, тому що в більшості практичних випадків функція трудомісткості залежить як від кількості даних на вході, так і від їхніх значень. У цьому випадку

f_n(n)≠const, g^*(n)≠1 =>

f_А(D) = f_n(n) · (D) або f_А(D) = f_n(n) + (D).

В якості приклада можна навести ряд алгоритмів чисельних методів, в яких параметрично-залежний зовнішній цикл по точності містить у собі кількісно-залежний фрагмент по розмірності, що породжує мультиплікативну форму для f_А(D).

 

В залежності від ступеня впливу кількісної і параметричної складових на головний порядок функції трудомісткості виділяють наступні підкласи у класі кількісно-параметричних алгоритмів:

3.1. ПідкласNPRL (Low)– підклас алгоритмів, трудомісткость яких слабо залежить від параметричної складової.

g⁺(n)=O(f_n (n)) <=> g^*(n)= Ө(1).

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

3.2. ПідкласNPRE (Equivalent ) – підклас алгоритмів, у трудомісткості яких складова g^*(n) має порядок росту, не перевищуючий f_n (n):

g^*(n)= Ө(f_n (n)) <=> g⁺(n)=Ө( (n)).

Таким чином, для алгоритмів цього підкласу вплив на головний порядок функції трудомісткості параметричного компоненту має той самій порядок (в мультиплікативній формі), що й кількісного компоненту. Для алгоритмів, що відносяться до цього підкласу, можна говорити про квадратично-кількісну функцію трудомісткості.

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

g⁺(n)= Ө(n²), f_n (n)= Ө(n).

3.3. ПідкласNPRH (High)– підклас алгоритмів, у трудомісткості яких складова g^*(n) має асимптотичний порядок росту вищий, ніж f_n (n):

g^*(n)= Ω(f_n (n))

Для алгоритмів цього підкласу саме параметричний компонент визначає головний порядок функції трудомісткості. Можна говорити, що ці алгоритми є кількісно-сильно-параметричними по функції трудомісткості алгоритмами.

У цей підклас входять, наприклад, алгоритми точного розв'язання NP-повних задач.

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