Логарифм

Материал из Algocode wiki
Перейти к: навигация, поиск

Определение:
логарфим по основанию a от b —это число $c$, такое что $a ^ c = b$

Иными словами, логарифм числа $b$ по основанию $a$ - это количество раз, которое можно делить число $b$ на $a$, пока резальтат не стал меньше единицы. Однако заметим, что такое определение менее универсальное, так как логарифм может быть дробным числом, а также отрицательным. Но для лучшего интуитивного восприятия можно помнить про это объяснение.

Обозначение: $\log_a b$. Логарифм определен только для $a > 0, b > 0, a \neq 1$.

Так как нам наиболее интересен логарифм во время оценки времени работы алгоритмов, то договоримся в асимптотиках использовать просто $\log n$, не указывая основание. Связано это с тем, что любые два логарифма числа $n$ по двум разным основаниям будут отличаться друг от друга в константу раз. То есть на рост функции относительно $n$ основание не влияет.

Утверждение: (Некоторые свойства логарифма)

  1. $\log_a b + \log_a c = \log_a (bc)$
  2. $\log_a b = -\log_a \frac{1}{b}$
  3. $\log_a b^c = c \log_a abs(b)$
  4. $\log_a n = \dfrac{\log_b n}{\log_b a}$.



Доказательство остаётся читателю в качестве упражнения



Автор конспекта: Полина Романченко

По всем вопросам пишите в telegram @Romanchenko