Предположим, что у нас есть запись вида:
log 2 (8)
Она звучит, как логарифм 8 по основанию 2. Данное выражение равно степени, в которую нам необходимо возвести число 2, чтобы получилось 8. Ответ в данном случае – 3.
2 ^ x = 8
x = 3
log 2 (8) = 3
Крайне простая математика.
Так какое отношение имеют логарифмы к алгоритмам? Здесь на помощь к нам может прийти алгоритм бинарного поиска.
Например, мы имеем массив целых чисел и мы знаем, что массив отсортирован по возрастанию. И нам необходимо найти число по значению. Мы можем пройтись по всем элементам массива и в этом случае, сложность данного подхода будет O(n). Т.е. в худшем случае, мы пройдёмся по массиву и не найдём искомое значение.
Но, так как мы знаем, что массив отсортирован, мы можем поделить его пополам и понять, в какой части массива наше число, слева или справа. И будем повторять эту операцию, пока не найдём искомое число.
Т.е. мы постоянно делим массив пополам. Вопрос, сколько раз нам придётся выполнить данную операцию? Вот здесь и приходит на помощь логарифм.
log 2 (n)
Например, мы получили на вход массив на 1 000 000 элементов. При данном подходе количество обращений к массиву в худшем случае –
log 2 (1 000 000) = 19.9315685693 = ~20 раз. Крайне не плохо.
Но, более интересен пример на 1 000 000 000 элементов:
log 2 (1 000 000 000) = 29.897352854 = ~ 30
Т.е. в 1000 раз больше элементов, но, только на 10 обращений больше.
С данной сложностью мы будем ещё не раз сталкиваться в разных структурах данных.
И по аналогии с коэффициентами, мы “опускаем” основание логарифма и всегда пишем только:
O (log n).
Вывод: логарифмы активно используются при оценке сложности алгоритмов. Алгоритмы с данной сложностью – крайне эффективны на больших входных данных.