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

       Каждый алгоритм в зависимости от реализации имеет определенную сложность вычисления.  Чаще всего под сложностью вычисления понимают количество времени необходимое алгоритму для решения задачи. В настоящее время принято использовать следующие виды оценок сложности вычисления (Классы сложности):

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

        Задача оценки сложности алгоритма заключается в анализе сложности вычисления для разных наборов входных данных (разный объем, порядок и т.д. ). Для каждого алгоритма перед началом его реализации необходимо получить следующие виды оценок:

  1. Наилучшая сложность вычисления.
  2. Средняя сложность вычисления.
  3. Наихудшая сложность вычисления.