Тема 8. Алгоритмы восстановления зависимостей.
В ряде случаев неизвестна структура программы, и можно лишь определить время ее работы при различных размерах входных данных T(N) (сек.)
Для построения аналитической зависимости сложности программы оценивают функцию T(N) на некотором интервале [Nmin, Nmax]. Затем проводят аппроксимацию найденной кривой некоторой аналитической функции с изменением параметров функции и оценкой ошибки аппроксимации.
Как
правило, в качестве такой функции
используют известные функции временной
сложности: O(n!),
O(XN),
O(NX),
O(logN),
O(
).
Этого достаточно для приближенной оценки сложности.
Если известны несколько функций аппроксимации, дающие примерно одинаковую точность, то выбирают ту из них, которая имеет минимальную сложность в качестве (N), а с максимальной сложностью – в качестве O(N).
Пример 1:
В
результате эксперимента над программой
была получена таблица временных
сложностей:
-
N
T1, сек.
T2, сек.
100
~ 0,1
~ 0,1
200
1,5
2,3
500
3,9
5,9
1000
7,6
11,9
5000
31
6,1
10000
68
173
20000
147
472
В результате поиска аппроксимации функции была получена следующая аналитическая зависимость:
Пример 2:
Часто бывает, что на время работы одного и того же алгоритма кроме размера задачи влияют другие параметры, вводимые пользователем.
В этом случае строят семейство функций аппроксимации и находят аналитически сложность алгоритма.
-
N
=5
=10
=15
25
8
2
1
50
32
4
2
75
88
7
3
100
250
10
4
125
720
13
5,5
150
200
18
7
175
5400
23
8,5
200
15000
30
10
