Экспоненциальные функции

Экспоненциальные функции записываются в форме f (n) = rn для некоторого постоянного основания r. Здесь нас интересует случай r > 1, что приводит к исключительно быстрому росту функции.

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

(2.9) Для всех r > 1 и всех d > 0 выполняется условие nd = O(rn).

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

По аналогии с записью O(log n) без указания основания часто встречаются формулировки вида «Алгоритм имеет экспоненциальное время выполнения» без указания конкретной экспоненциальной функции. В отличие от свободного использования log n, оправданного игнорированием постоянных множителей, такое широкое использование термина «экспоненциальный» несколько неточно.

В частности, для разных оснований r > s > 1 никогда не выполняется условие r n = Θ(sn). В самом деле, для этого бы потребовалось, чтобы для некоторой константы c > 0 выполнялось условие rn ≤ csn для всех достаточно больших n.

Но преобразование этого неравенства дает (r/s)n ≤ c для всех достаточно больших n. Так как r > s, выражение (r/s)n стремится к бесконечности с ростом n, поэтому оно не может ограничиваться константой c.

Итак, с асимптотической точки зрения все экспоненциальные функции различны. Тем не менее обычно смысл неточной формулировки «Алгоритм имеет экспоненциальное время выполнения» понятен — имеется в виду, что время выполнения растет по крайней мере со скоростью некоторой экспоненциальной функции, а все экспоненциальные функции растут так быстро, что алгоритм можно попросту отбросить, не вдаваясь в подробности относительно точного времени выполнения.

Это не всегда оправданно — в некоторых случаях за экспоненциальными алгоритмами скрывается больше, чем видно на первый взгляд (как мы увидим, например, в главе 10); но как указано в первой части этой главы, это разумное эмпирическое правило.

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