истанням загальновідомих елементарних функцій (або, як кажуть, в аналітичному вигляді). Вихід полягає в наступному. Безліч D комбінацій вихідних даних таки розбивається "яких-небудь розумним чином" на класи, і кожному класу приписується деяке значення змінної V. Наприклад, якщо ми хочемо оцінити складність алгоритму аналізу арифметичних виразів, то в один клас можна помістити всі вирази, які з однакового числа символів (рядки однакової довжини) і змінну V зробити рівною довжині рядка. Це розумне припущення, оскільки із збільшенням довжини складність повинна збільшуватися: пріпішем до вираження довжини n рядок +1 - вийде вираз довжини n +2, що вимагає для аналізу більше операцій, ніж попереднє. Але суворого (лінійного) порядку немає. Серед виразів довжини n може знайтися більш складне (у сенсі аналізу), ніж деякий вираз довжини n +2, не кажучи вже про те, що серед виразів рівної довжини будуть вираження різної складності. p align="justify"> Потім для кожного класу (з даними значенням V) оцінюється кількість необхідних операцій в гіршому випадку, тобто для набору вихідних даних, що вимагають максимальної кількості операцій обробки (складність для гіршого випадку - верхня оцінка), і в кращому випадку - для набору, що вимагає мінімальної кількості операцій. Таким чином, виходять верхня і нижня оцінки складності алгоритму (малюнок 1). br/>В
Рис.1. Залежність складності алгоритму від складності даних
Різниця між Tmax (V) і Tmin (V) може бути значною. Але для багатьох алгоритмів відзначається ситуація "рідкості крайніх значень": тільки на відносно невеликій кількості поєднань вихідних даних реалізуються близькі до верхніх або нижнім оцінками значення складності. Тому цікаво буває відшукати деяке "усереднене" за всіма даними число операцій (середня оцінка). Для цього залучаються комбінаторні методи або методи теорії ймовірностей. Отримане значення і вважається значенням Тa (V) середньої оцінки. p> Системи реального часу, що працюють в дуже критичних умовах, вимагають, щоб нерівність Тa (X)
4. Основні методи і прийоми аналізу складності
Відшукання функції складності проводиться на основі аналізу тексту алгоритму. Для визначеності будемо вважати, що алгоритм записаний на універсальній мові програмування типу Паскаля і містить явно записані арифметичні операції, операції порівняння і пересилки скалярних даних, керуючі конструкції циклів і вибору. Якщо зустрічаються виклики процедур, то виклик не розглядається як одна операція: виклик вносить внесок у загальну суму на основі підрахунку кількості ...
