Отличие линейного от экспоненциального роста
При экспоненциальном росте величина растёт тем быстрее, чем больше её значение. При линейном росте она увеличивается на фиксированное значение.
Легче понять на примерах. Мы будем строить две последовательности чисел: линейную и экспоненциальную.
Пусть начальное значение для первой последовательности будет 1. Каждое последующее значение мы будем получать, добавляя к предыдущему 1, или любое другое число. Получится последовательность: 1, 2, 3, 4, … Это линейный рост, 50-й элемент такой последовательности будет равен 50, а график выглядеть как прямая восходящая линия.
Теперь, для второй последовательности, возьмём в качестве начальных значений два числа - 2 и 1, X и Y. Двойка (X) останется неизменной, это будет основание степени, а Y будет показателем степени, в которую мы будем возводить. Для каждого следующего числа будем просто прибавлять 1 к Y. Таким образом первое число будет 21 = 2, второе 22 = 4, третье 23 = 8 и так далее. В этом случае 10-й элемент будет равен 1 024, 20-й равен 1 048 576, а 50-й равен уже 1 125 899 906 842 624. Т.е. мы видим взрывной рост по мере увеличения последовательности. График наглядно демонстрирует это.
Экспоненциальный рост кажется медленным на начальных этапах, но со временем он значительно превосходит линейный. В связи с этим есть задачи, которые не под силу классическим компьютерам за приемлемый промежуток времени, потому что для каждой последующей итерации будет требоваться условно добавление еще одного суперкомпьютера. На этом основаны также многие криптографические алгоритмы.
Оба графика используют логарифмическую шкалу для наглядности.