Степени, логарифмы и порядок роста

Если ты без калькулятора знаешь, что log₂ миллиона около двадцати, а 2^n при n = 100 не посчитать никогда, листай до «Теперь сам» в конце.

Как думаешь, сколько нужно вопросов

Я загадал число от одного до миллиарда. Ты задаёшь вопросы «больше ли оно, чем ...?», я отвечаю «да» или «нет». Ответь себе до того, как читать дальше: сколько вопросов понадобится в худшем случае? Тысяча? Миллион? Ответ - тридцать, и вся первая половина урока объясняет, откуда это число и почему оно такое маленькое.

На что это похоже

Турнир на выбывание. В каждом круге играют пары, и половина участников уходит. При 1024 участниках кругов будет 10: 1024, 512, 256, ..., 2, 1. Добавь участников вдвое - кругов станет на ОДИН больше. Число кругов турнира - это и есть логарифм числа участников. А обратная задача - сколько участников выдержит турнир из k кругов - это степень: каждый лишний круг удваивает число мест.

Механизм: степень и логарифм - один счёт в две стороны

Степень 2^k - произведение k двоек: 2^3 = 2 · 2 · 2 = 8. В Python пишется 2 ** k, в тексте курса иногда 2³ или 2ⁿ. Удвоение растёт пугающе быстро, и три опорные точки стоит помнить наизусть:

Логарифм по основанию два - обратный счёт: log₂ n это такое k, что 2^k = n, то есть сколько раз n делится пополам до единицы. log₂ 8 = 3, потому что 8 → 4 → 2 → 1. Для n, которое не является степенью двойки, логарифм дробный (log₂ 1000 ≈ 9.97), а число делений нацело - это логарифм, округлённый вниз. Округление вниз пишут ⌊x⌋, вверх - ⌈x⌉: ⌊9.97⌋ = 9, ⌈9.97⌉ = 10.

Почему в оценках алгоритмов стоит именно логарифм, а не что-то другое: деление пополам до единицы и ЕСТЬ логарифм по определению. Где алгоритм на каждом шаге отбрасывает половину - двоичный поиск, сбалансированное дерево, турнир, - там и появляется log₂ n.

Два свойства понадобятся постоянно. log₂(a · b) = log₂ a + log₂ b, потому что при умножении степеней показатели складываются: 2^x · 2^y = 2^(x+y). Отсюда удвоить данные значит добавить один шаг: log₂(2n) = 1 + log₂ n. И основание почти не важно: n = 10^(log₁₀ n), а 10 ≈ 2^3.32, поэтому log₂ n ≈ 3.32 · log₁₀ n - логарифмы по разным основаниям отличаются в постоянное число раз, и в оценках часто пишут просто log n.

Правило

2^k - k удвоений, log₂ n - сколько раз делить n пополам до единицы; одно обратно другому. 2^10 ≈ 10^3, отсюда log₂ тысячи около 10, миллиона около 20, миллиарда около 30. Порядок роста - как число шагов растёт с размером данных, и на больших данных он решает всё, а константа - почти ничего.

Разбор: сколько раз делится пополам

Проверим счёт делений на настоящих числах. Встроенный n.bit_length() - 1 даёт тот же ответ другим способом - через число двоичных цифр, о которых следующий урок:

for n in [1, 2, 8, 1000, 10 ** 6, 10 ** 9]:
    k = 0
    m = n
    while m > 1:
        m = m // 2
        k = k + 1
    print(n, k, n.bit_length() - 1)

1 0 0
2 1 1
8 3 3
1000 9 9
1000000 19 19
1000000000 29 29

Миллиард делится пополам нацело 29 раз, и тридцатый вопрос в игре «угадай число» нужен, чтобы из двух оставшихся кандидатов выбрать один. Обрати внимание: данные выросли в миллиард раз, а число шагов - с нуля до 29. Это и делает логарифмические алгоритмы такими ценными.

Разбор: пять ступеней роста

Сравним, сколько шагов нужно алгоритмам разного порядка роста. n log n получается, когда на каждый из n элементов уходит около log n шагов: так работают лучшие сортировки, о них свой раздел. У 2ⁿ число такое, что печатаем только, сколько в нём цифр. Модуль math входит в сам Python, ставить его не надо:

import math

print("       n  log n    n log n             n²  2ⁿ: цифр")
for n in [10, 100, 1000, 10 ** 6]:
    lg = math.log2(n)
    cifr = int(n * math.log10(2)) + 1
    print(f"{n:>8} {lg:>6.1f} {n * lg:>10.0f} {n * n:>14} {cifr:>9}")
print(math.log(1000, 10), int(math.log(1000, 10)))

       n  log n    n log n             n²  2ⁿ: цифр
      10    3.3         33            100         4
     100    6.6        664          10000        31
    1000   10.0       9966        1000000       302
 1000000   19.9   19931569  1000000000000    301030
2.9999999999999996 2

Запись f"{n:>8}" - строка, в которую вставлено значение n, выровненное вправо по ширине 8; .1f добавляет «одна цифра после точки», .0f - «без дробной части». Число цифр у 2ⁿ программа считает без самого 2ⁿ: у числа m десятичных цифр ⌊log₁₀ m⌋ + 1, а log₁₀ 2ⁿ = n · log₁₀ 2 по тому же правилу «логарифм произведения - сумма логарифмов». Последняя строка вывода к таблице не относится - о ней ниже. Переведём таблицу в секунды на машине, делающей миллиард простых шагов в секунду. На миллионе элементов n log n - две сотых секунды, n² - около семнадцати минут. А 2ⁿ уже при n = 100 - число из 31 цифры: столько шагов не сделать за время существования Вселенной. Разница между соседними ступенями на больших данных - не «в несколько раз», а «готово сразу» против «не дождаться».

Что ломается без этого

Последняя строка вывода rost.py - 2.9999999999999996 2. Логарифм тысячи по основанию десять равен трём, но дробные числа хранятся неточно, и int() отрезает дробную часть - получается 2. Для целых логарифмов по основанию два надёжнее n.bit_length() - 1 или цикл делением, как в первом разборе. Вторая ошибка - путать округления: двоичных цифр у числа ⌊log₂ n⌋ + 1, а не ⌈log₂ n⌉, и на степенях двойки эти формулы расходятся (у 8 цифр четыре: 1000). Третья - считать экспоненту «просто большим числом» и надеяться на быструю машину: удвоение скорости машины даёт алгоритму 2ⁿ ровно один лишний элемент.

Зачем это в работе

Оценка на салфетке до написания кода. Индекс по миллиарду записей - около тридцати сравнений на поиск, значит, вопрос не в процессоре, а в том, сколько из этих тридцати сходят на диск. Сравнение каждого пользователя с каждым на миллионе пользователей - полтриллиона разных пар, и это не «оптимизировать», а передумать. Перебор всех подмножеств из сорока признаков - триллион вариантов, из шестидесяти - невозможно. Привычка прикидывать log, n² и 2ⁿ в уме отсекает плохое решение раньше, чем на него потрачен день.

Теперь сам

Сколько раз можно поделить 5000 пополам нацело, пока не останется единица? И во сколько раз вырастет время алгоритма с порядком n², если данных станет в десять раз больше?