Критерии оценки эффективности алгоритмов

Эффективность алгоритма принято оценивать количеством элементарных операций, например сравнений, которые необходимо выполнить для решения задачи, а также количеством памяти, которая требуется для выполнения алгоритма. При оценке эффективности алгоритмов не ограничиваются массивом с фиксированным количеством элементов, а пытаются вывести формулу эффективности алгоритма для массивов произвольной длины. Такой анализ включает изучение ситуаций, в которых алгоритм демонстрирует свои наилучшие свойства, ситуаций, когда его эффективность минимальна, а также оценку его средней производительности.

Название алгоритма	Минимальное число сравнений	Среднее число сравнений	Максимальное число сравнений
Сортировка включением	n-1	(n² + n - 2)/4	(n² - n)/2 - 1
Сортировка выбором	(n² - n)/2	(n² - n)/2	(n² - n)/2
Обменная сортировка	(n² - n)/2	(n² - n)/2	(n² - n)/2
Последовательный поиск	1	(n + 1)/2	n
Двоичный поиск	1	(log₂(n)+1)/2	log₂(n)

Вид функциональной зависимости, которая связывает количество элементов массива и максимальное число сравнений, определяет класс алгоритма. Класс алгоритма принято обозначать буквой Θ. Например, алгоритмы сортировки относятся к классу Θ(n2), алгоритм последовательного поиска относится к классу Θ(n), а алгоритм двоичного поиска - к классу Θ(lg n). Формы графиков соответствующих перечисленным классам алгоритмов приведены на рисунке.

Чем ниже эффективность наилучшего из всех известных алгоритмов решения конкретной задачи, тем выше алгоритмическая сложность этой задачи, тем больше времени и сил потребуется для ее решения.

Формы графиков соответствующие различным классам алгоритмов: