2018-01-08
1576
Способы оценки сложности:
1) Экспериментальные исследования.
Основные требования:
- множество разнообразных тестов с неповторяющимися закономерностями;
- в наборе тестов должны присутствовать все «крайние» случаи;
- преимущество «обычных» входных данных.
Основные недостатки:
- сложность экстраполяции на другие объемы данных;
- занимает длительное время;
- результаты сильно зависят от конкретной реализации.
2) Теоретическая оценка.
Важно уметь строить теоретическую оценку сложности алгоритма. Кроме того, для приближенных алгоритмов важно оценивать точность приближенного решения.
На сложность алгоритма может влиять не только сама задача, но и ограничения на входные данные.
Понятие сложности алгоритмов:
1) Временная: оценивается
2) Емкостная: характеризует объем памяти, необходимый для хранения входных и выходных данных и промежуточных результатов.
x – входные данные
tα(х) – функция сложности – оценка времени работы алгоритма на входных данных х.
|
|
|
Перейдем от х к характеристике входных данных v(x), которую будет называть объемом (сложностью) входных данных.
tα(v) – сложность алгоритма
Пример:
function (n: integer): integer
vari,p: integer;
begin
p:=1; 1 оп
for i:=2 to n do p:=p*I n-1разпо 2
f:=p; 1 оп
end;
итого: 1+(n-1)*2+1=2nопераций
V(n) –значение числа n
tα(v)=2n
Верхняя (нижняя) оценка сложности алгоритма 
(t α(v)) –это функция, отражающая максимальное (минимальное) количество операций, выполняемое алгоритмом при поступлении на вход данных объемом V, т.е. это их оценка в худшем (лучшем) случае.
Средняя оценка сложности 
- это функция, отражающая среднее количество операций, выполняемое алгоритмом при поступлении на вход данных объемом V, при этом при вычислении среднего количества учитывается вероятность появления тех или иных входных данных.
По умолчанию подразумевают среднюю оценку сложности. Ее сложнее всего получить.
Если не оговорено отдельно, то за одну условную операцию будем считать каждую арифметическую или логическую операцию, а также операции пересылки данных.
