Логарифмическая зависимость

Чтобы изучать алгоритмы дальше, нужно вспомнить, что такое логарифм и экспонента.

Логарифм числа b по основанию a — это показатель степени, в которую нужно возвести a, чтобы получить b.

x = logₐ(b) можно вычислить, решив уравнение aˣ = b.

Например, log₂(8) будет равен трём, ведь чтобы получить восемь, нужно возвести два в третью степень. Просто, не правда ли?

Но зачем вообще нужны логарифмы? Если вам кажется, что они не встречаются в повседневной жизни, то это не так!

Без логарифмов не обойтись в навигации. Мореплаватели применяют их, чтобы прокладывать курс, учитывая расстояние до порта назначения, скорость ветра и течения, кривизну поверхности Земли и другие факторы.

В астрономии тоже применяют логарифмы. Делая сложные расчёты, приходится одновременно учитывать огромные расстояния между объектами, их взаимное расположение, светимость и массу, а также различные коэффициенты для планет и звёзд.

Можно привести и более бытовой пример. Одну и ту же разницу звукового давления между тихими звуками заметить проще, чем между громкими. Например, в соседней комнате телевизор может работать так тихо, что слов не разобрать. Но стоит немного прибавить звук, и вы отчётливо услышите, о чём говорят в эфире. А если на рок-концерте бас-гитара зазвучит громче на такую же величину, на какую прибавили громкость телевизора, зрители разницы не заметят. Дело в том, что интенсивность восприятия прямо пропорциональна натуральному логарифму силы раздражителя. Этот закон получил название Вебера-Фехнера.

Далековато от программирования? В IT-сфере логарифмы тоже применяют! Функциями, которые их содержат, выражают эффективность многих распространённых алгоритмов. С такими алгоритмами вы будете часто встречаться в курсе.

Представьте, что ищете слово в словаре. Вряд ли вы станете листать страницу за страницей, начиная с первой, — ведь слова отсортированы по алфавиту. Лучше открыть книгу примерно посередине. Если вы попали на страницу с нужным словом, алгоритм завершён. Если же слово находится раньше открытой страницы, вы откроете словарь примерно в середине первой половины, а если после — в середине второй. И так до окончания поиска.

Если страниц в словаре 100, и вы воспользуетесь предложенным алгоритмом, достаточно будет просмотреть максимум семь страниц.

Это логарифм по основанию два от 100. На самом деле log₂(100) примерно равен 6,64, но нас интересуют целые числа, так как число просмотров не может быть дробным.

Разберёмся, почему получается именно логарифм.

Если страниц 100, то делить пополам, пока не дойдём до одной страницы, нужно максимум 7 раз. Каждый раз объём рассматриваемой части книги уменьшается вдвое, пока не получится всего одна страница. Можно развернуть алгоритм в обратную сторону. Имея одну страницу, нужно за какое-то количество итераций получить 100, на каждом шаге увеличивая объём вдвое.

Такой алгоритм поиска экономит время по сравнению с вариантом, где вы пролистываете словарь с первой страницы.

Этот алгоритм называется бинарным поиском. Далее вы ещё не раз с ним встретитесь.

На рисунке приведены графики функций зависимости количества операций сравнения от количества страниц для линейного и бинарного поиска.

Основные формулы, которые могут пригодиться при работе с логарифмами:

Каждый раунд количество игроков будет уменьшаться вдвое. В последнем раунде остаются два теннисиста, которые сыграют один матч, а в первом раунде будет всего 128 матчей. На каждом шаге их количество уменьшается вдвое. Таким образом, нужно найти log₂(128), что равно 7.

В первом раунде будет сыграно 128 матчей, ведь разбив 256 игроков по парам, получим 128. Из каждого матча лишь один игрок перейдёт на следующий этап. Значит, в следующем круге окажутся 128 человек. Разделим их по парам и получим 64 матча. Так же нужно считать до финала, где будут играть 2 теннисиста. Чтобы вычислить общее количество матчей, нужно сложить их число на каждом этапе: 128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = 255.