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

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

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

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

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

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

По аналогии с записью О(log n) без указания основания часто встречаются формулировки вида «Алгоритм имеет экспоненциальное время выполнения» без указания конкретной экспоненциальной функции. В отличие от свободного ис- пользования log n, оправданного игнорированием постоянных множителей, такое широкое использование термина «экспоненциальный» несколько неточно. В част- ности, для разных оснований r > 5 > 1 никогда не выполняется условие rn = θ(s"). В самом деле, для этого бы потребовалось, чтобы для некоторой константы с > 0 выполнялось условие rn < csn для всех достаточно больших n. Но преобразование этого неравенства дает (r/s)n < c для всех достаточно больших n. Так как r > s, вы- ражение (r/s)n стремится к бесконечности с ростом n, поэтому оно не может огра- ничиваться константой с.

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

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

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

2.3.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Экспоненциальные функции:

  1. Функции журналистики. Понятие функцию Многообразие социальных и информационных потребностей общества – объективная основа функций журналистики.
  2. “Не язык — функция поэта, а поэт — функция языка”
  3. 1.1.2. Функции социологии
  4. РЕЧЬ: ФУНКЦИЯ ПРЕДИКАТИВНАЯ
  5. ФУНКЦИЯ ПСИХИЧЕСКАЯ НАТУРАЛЬНАЯ
  6. ФУНКЦИЯ ПСИХОФИЗИОЛОГИЧЕСКАЯ
  7. Иерархия функций
  8. Функции управления в организации.
  9. ФУНКЦИЯ ВЕГЕТАТИВНАЯ
  10. Тема 4. Функции сравнительного правоведения
  11. ФУНКЦИЯ ПСИХИЧЕСКАЯ: ЛОКАЛИЗАЦИЯ
  12. Дисфункции и латентные функции
  13. 11.2.3. Функции религии
  14. Функции типа
  15. ФУНКЦИИ КОНТРОЛЯ
  16. Функции телевидения