Порядок роста алгоритма - EcsFlash/DataTypes GitHub Wiki

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

Зачем вообще говорить про порядок роста.

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

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