Экспоненциальные функции
Экспоненциальные функции записываются в форме f (n) = rn для некоторого по- стоянного основания r. Здесь нас интересует случай r > 1, что приводит к исклю- чительно быстрому росту функции.
(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); но как указано в первой части этой главы, это разумное эмпирическое правило.
Итак, логарифмические, полиномиальные и экспоненциальные функции служат полезными ориентирами в диапазоне функций, встречающихся при анализе времени выполнения. Логарифмические функции растут медленнее полиномиаль- ных, а полиномиальные растут медленнее экспоненциальных.
- Алгоритмы, которые работают бесконечно
- Бесконечные пространства выборки
- Независимые события
- Конечные вероятностные пространства
- Простой рандомизированный план
- Планы и их продолжительность
- Анализ алгоритмов маркировки
- Достижение линейного ожидаемого времени выполнения
- Структура данных для хранения подквадратов
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу