Логарифмические функции

Напомним, что логарифм n по основанию b — logb n — равен такому числу х, что bx = n. Чтобы получить примерное представление о скорости роста logb n, можно заме- тить, что при округлении вниз до ближайшего целого числа логарифм на 1 меньше количества цифр в представлении n по основанию b (таким образом, например, значение 1 + log2 n с округлением вниз определяет количество битов, необходимых для представления n).

Итак, логарифмические функции растут очень медленно. В частности, для каждого основания b функция logb n асимптотически ограничивается всеми функ- циями вида nx, даже для (дробных) значений х, сколь угодно близких к 0.

(2.8) Для всех b > 1 и всех х > 0 выполняется условие logb n = O(nx).

Логарифмы могут напрямую преобразовываться к другому основанию по сле- дующей фундаментальной формуле:


Эта формула объясняет, почему границы часто записываются в виде О(log n) без указания основания логарифма. Не стоит рассматривать это как неточность

записи: из приведенной формулы следует, что log л = —--------------- !ogfr п, а это означает,

⅛А в

что loga n = θ(⅛ь n). Следовательно, при использовании асимптотической записи основание алгоритма роли не играет.

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

Еще по теме Логарифмические функции:

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