Оценка и сложност на алгоритмите. Лекция

Оценка и сложност на
алгоритмите
Лекция 3

Дисциплина: Синтез и анализ на алгоритми

Доц. Е. Сотирова

Сложност на алгоритъм
Чрез анализиране на сложността може да
се сравняват алгоритмите и избере поефективния.
 Времева сложност – бързодействие
 Сложност по памет – необходимата
памет
 Дефиниционна област - множеството от
входни данни
 Точност - каква е максималната грешка,
която алгоритъмът допуска – всеки
числен метод има грешка в % (не се
отнася за алгоритмите, работещи с цели
числа и символна информация)

Размер на входните данни
1)
2)
3)
4)
5)

n = 100;
sum = 0;
for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
sum++;

Скорост на изпълнение
При увеличаване 10 пъти на
n, времето за изпълнение се
увеличава 100 пъти.

n=10

0.000001 сек.

n=100

0.0001 сек.

n=1000

0.01 сек.

n=10000

1.071 сек.

n=100000

106.543 сек.

n=1000000

10663.6 сек.

*Наков, П., П. Добриков, Програмиране = ++Алгоритми, София, 2005

Пример*