Алгоритм — набор инструкций, описывающих порядок действий исполнителя для достижения некоторого результата.

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

Важен порядок роста времени выполнения алгоритма в зависимости от n

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

Виды анализа: математический и эмпирический

Измерение времени выполнения алгоритма

1. Непосредственное (эмпирический анализ)

2. Определение количества базовых операций, которые должен выполнить алгоритм при обработке входных данных размера n (математический анализ)

Порядок роста

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

Эффективность алгоритма в разных случаях

Существует большое количество алгоритмов, время выполнения которых зависит не только от размера входных данных, но и от конкретных особенностей входных данных (пример – поиск).

Эффективность измеряют для:

Пример: среднее количество операций сравнения при поиске:

Итак:

При разработке алгоритмов очень важно иметь возможность оценить ресурсы, необходимые для проведения вычислений, результатом оценки является функция сложности (трудоемкости). Оцениваемым ресурсом чаще всего является процессорное время (вычислительная сложность) и память (сложность алгоритма по памяти). Оценка позволяет предсказать время выполнения и сравнивать эффективность алгоритмов.