29 марта 2010
18 марта 2010
17 января 2010
07 декабря 2009
15 октября 2009
Каждый алгоритм в зависимости от реализации имеет определенную сложность вычисления. Чаще всего под сложностью вычисления понимают количество времени необходимое алгоритму для решения задачи. В настоящее время принято использовать следующие виды оценок сложности вычисления (Классы сложности):
№ п.п.(От сложного к простому) | Название сложности | Мат. формула | Примеры алгоритмов |
1 | Факториальная | N! | Алгоритмы комбинаторики (сочетания, перестановки и т.д.) |
2 | Экспоненциальная | KN | Алгоритмы перебора (brute force) |
3 | Полиномиальная | NK | Алгоритмы простой сортировки (buble sort) |
4 | Линейный логарифм | N * log(N) | Алгоритмы быстрой сортировки (heap sort) |
5 | Линейная | K * N | Перебор элементов массива |
6 | Логарифмическая | K * log(N) | Бинарный поиск |
7 | Константная | К | Обращение к элементу массива по индексу |
Задача оценки сложности алгоритма заключается в анализе сложности вычисления для разных наборов входных данных (разный объем, порядок и т.д. ). Для каждого алгоритма перед началом его реализации необходимо получить следующие виды оценок: