Мини-напоминание: показательная функция возрастает в разы быстрее, чем логарифм

Логарифмы и их применение

Рассмотрим ключевые области применения логарифмов в алгоритмах.

Логарифмы и двоичный поиск

Двоичный поиск — классический пример алгоритма с логарифмической временной сложностью $O(log_2 n)$.

Про двоичный поиск можете прочитать в статье 05.01.181 Двоичный поиск

Пример: Представьте, что нужно найти человека по имени в телефонной книге, содержащей миллион имён. Вместо последовательного перебора (который занял бы огромное время), вы открываете книгу посередине. Сравнивая искомое имя с выбранным, вы отбрасываете половину книги. Повторяя этот процесс, количество страниц сокращается вдвое на каждом шаге.

Количество таких делений для книги из n записей равно $log_2 n$. Таким образом, чтобы найти любого человека в телефонной книге на миллион имён, достаточно всего двадцати сравнений. Этот принцип является одним из наиболее плодотворных в разработке алгоритмов.

Логарифмы и деревья

Логарифмы естественным образом возникают при анализе древовидных структур данных.

Рассмотрим дерево, в котором каждый узел имеет d потомков (для двоичных деревьев $d = 2$). Дерево высотой в один уровень может иметь d листьев, высотой в два уровня — $d^2$ листьев. В общем случае, зависимость количества листьев n от высоты дерева h выражается формулой: $n = d^h$ Отсюда следует, что высота дерева находится по формуле: $h = log_d n$

Про двоичные деревья поиска можете прочитать в статье 03.04.108 Двоичные деревья поиска

Логарифмы и биты

Логарифмы тесно связаны с представлением информации в двоичном виде.

Предположим, имеются две однобитовые комбинации (0, 1), четыре двухбитовые (00, 01, 10, 11) и восемь трёхбитовых комбинаций. Сколько битов w потребуется, чтобы представить любую из n различных комбинаций?

Количество различных битовых комбинаций удваивается с добавлением каждого бита. То есть $2^w = n$. Следовательно, необходимое количество битов вычисляется как: $w = log_2 n$

Логарифмы и умножение

Вспомним, что $log_b(xy) = log_b(x) + log_b(y)$, т.е. логарифм произведения равен сумме логарифмов сомножителей. Прямым следствием этого является формула $log_a n^b = b*log_a n$.

Выясним, как вычислить $a^b$ для любых a и b, используя функции $exp(x)$ и $ln(x)$ на карманном калькуляторе, зная, что $exp(x) = e^x$ и $ln(x) = log_e(x)$. Таким образом, вычисление $a^b = exp(ln(a^b)) = exp(b*ln a)$.

То есть задача сводится к одной операции умножения с однократным вызовом каждой из этих функций.

Быстрое возведение в степень

(тут кто-нибудь другой)

Логарифмы и сложение