Основы анализа алгоритмов

"Анализ алгоритмов" означает процесс исследования эффективности алгоритмов, которую можно оценить по двум параметрам: времени выполнения алгоритма и требуемому объему оперативной памяти.

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

Существует два вида эффективности: временной и пространственной. Временная эффективность является индикатором скорости работы алгоритма. Пространственная эффективность показывает, сколько дополнительной оперативной памяти нужно для работы алгоритма.

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

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

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