Алгоритмы восстановления зависимостей.

Тема 8.

В ряде случаев неизвестна структура программы, и можно лишь определить время ее работы при различных размерах входных данных T(N) (сек.)

Для построения аналитической зависимости сложности программы оценивают функцию T(N) на некотором интервале [N_min, N_max]. Затем проводят аппроксимацию найденной кривой некоторой аналитической функции с изменением параметров функции и оценкой ошибки аппроксимации.

Как правило, в качестве такой функции используют известные функции временной сложности: O(n!), O(X^N), O(N^X), O(logN), O().

Этого достаточно для приближенной оценки сложности.

Если известны несколько функций аппроксимации, дающие примерно одинаковую точность, то выбирают ту из них, которая имеет минимальную сложность в качестве W(N), а с максимальной сложностью – в качестве O(N).

Пример 1:

В результате эксперимента над программой была получена таблица временных сложностей:

В результате поиска аппроксимации функции была получена следующая аналитическая зависимость:

Пример 2: