прикладної, так і з теоретичної точок зору. У практиці проектування систем реального часу задача розробки програми формулюється так: відшукати такий алгоритм a, вирішальний завдання P, що Т a (X) ГЋ D, де D - область допустимих значень вхідних даних (завдання з обмеженням на тимчасову складність). У системах, де критерій якості пов'язаний з часом очікування реакції комп'ютера (системи управління базами даних, системи автоматичного перекладу для природних мов програми для гри в шахи та інші) завдання може бути поставлена ​​так: відшукати серед всіх алгоритмів, що вирішують завдання Р, такий алгоритм а , для якого функція T a (X) прийматиме мінімальні значення на обраному підмножині S значень вихідних даних, X ГЋ S ГЊ D (задача мінімізації часової складності; додатково формулюються обмеження за ємнісний складності).
Двоїста задача мінімізації ємнісний складності при обмеженнях на тимчасову складність виникає рідше чинності архітектурних особливостей сучасних ЕОМ, оскільки запам'ятовуючі пристрої різних рівнів, що входять до складу машини, побудовані так, що програмі може бути доступна дуже велика, практично необмежена область пам'яті - віртуальна пам'ять. Недостатня кількість основної пам'яті призводить лише до деякого уповільнення роботи через обмінів з диском. Так як в будь-який момент часу програма працює лише з двома-трьома значеннями і використання кешу і апаратного перегляду команд програми вперед дозволяє завчасно перенести з диска в основну пам'ять потрібні значення, то можна констатувати, що мінімізація ємнісний складності не є першочерговим завданням.
3. Верхні і середні оцінки складності алгоритмів
Багато задач характеризуються великою кількістю вихідних даних. Вводячи інтегральний параметр V обсягу (складності) даних, неявно припущено, що всі безліч комбінацій значень вихідних даних може бути розбите на класи. В один клас потрапляють комбінації з одним і тим же значенням V. Для будь-якої комбінації із заданого класу алгоритм буде мати однакову складність (виконавець виконає одне і те ж кількість операцій). Інакше кажучи, функція c = сложность_ a (X) може бути розкладена в композицію функцій V = r (Х) і c = Т a (V), де r - перетворення значень x1, x2, x3, ..., xn в значення V (8, стор 117-119).
Але немає ніяких причин сподіватися, що це буде виконуватися для будь-яких алгоритмів, враховуючи наше бажання представляти функції формулами з викор...
