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

Тема 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:

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

N	T1, сек.	T2, сек.
	~ 0,1	~ 0,1
	1,5	2,3
	3,9	5,9
	7,6	11,9
		6,1

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

Пример 2:

Дата добавления: 2014-01-07