операцій. Ведемо наступні позначення (6, стор 77):
. Fa Г™ (N) - найгірший випадок - найбільша кількість операцій, що здійснюються алгоритмом А для вирішення конкретних проблем розмірністю N:
Г™ (N) = max {Fa (D)} - найгірший випадок на DN
. Fa Гљ (N) - кращий випадок - найменша кількість операцій, що здійснюються алгоритмом А для вирішення конкретних проблем розмірністю N:
Гљ (N) = min {Fa (D)} - кращий випадок на DN
. ` Fa (N) - середній випадок - середня кількість операцій, що здійснюються алгоритмом А для вирішення конкретних проблем розмірністю N:
` Fa (N) = (1/MDN) * ГҐ {Fa (D)} - середній випадок на DN
Залежно від впливу вихідних даних на функцію трудомісткості алгоритму може бути запропонована наступна класифікація, що має практичне значення для аналізу алгоритмів:
. Кількісно-залежні по трудомісткості алгоритм. Це алгоритми, функція трудомісткості яких залежить тільки від розмірності конкретного входу, і не залежить від конкретних значень:
(D) = Fa (| D |) = Fa (N)
Прикладами алгоритмів з кількісно-залежною функцією трудомісткості можуть служити алгоритми для стандартних операцій з масивами і матрицями - множення матриць, множення матриці на вектор і т.д.
. параметричний-залежні по трудомісткості алгоритми. Це алгоритми, трудомісткість яких визначається не розмірністю входу (як правило, для цієї групи розмірність входу зазвичай фіксована), а конкретними значеннями оброблюваних слів пам'яті:
Fa (D) = Fa (d1, ..., dn) = Fa (P1, ..., Pm), m ВЈ n
Прикладами алгоритмів з параметрично-залежної трудомісткістю є алгоритми обчислення стандартних функцій із заданою точністю шляхом обчислення відповідних статечних рядів. Очевидно, що такі алгоритми, маючи на вході два числових значення - аргумент функції і точність, виконують істотно залежне від значень кількість операцій. p align="justify">. Кількісно-параметричні по трудомісткості алгоритми. Однак у більшості практичних випадків функція трудомісткості залежить як від кількості даних на вході, так і від значень вхідних даних, в цьому випадку:
(D) = Fa (| | D | |, P1, ..., Pm) = Fa (N, P1, ..., Pm)
Як приклад можна навести алгоритми чисельних методів, в яких параметрично-залежни...
