Логарифм
Определение:
логарфим по основанию a от b —это число $c$, такое что $a ^ c = b$
Иными словами, логарифм числа $b$ по основанию $a$ - это количество раз, которое можно делить число $b$ на $a$, пока резальтат не стал меньше единицы. Однако заметим, что такое определение менее универсальное, так как логарифм может быть дробным числом, а также отрицательным. Но для лучшего интуитивного восприятия можно помнить про это объяснение.
Обозначение: $\log_a b$. Логарифм определен только для $a > 0, b > 0, a \neq 1$.
Так как нам наиболее интересен логарифм во время оценки времени работы алгоритмов, то договоримся в асимптотиках использовать просто $\log n$, не указывая основание. Связано это с тем, что любые два логарифма числа $n$ по двум разным основаниям будут отличаться друг от друга в константу раз. То есть на рост функции относительно $n$ основание не влияет.
Утверждение: (Некоторые свойства логарифма)
- $\log_a b + \log_a c = \log_a (bc)$
- $\log_a b = -\log_a \frac{1}{b}$
- $\log_a b^c = c \log_a abs(b)$
- $\log_a n = \dfrac{\log_b n}{\log_b a}$.
Доказательство остаётся читателю в качестве упражнения
Автор конспекта: Полина Романченко
По всем вопросам пишите в telegram @Romanchenko