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