Экспресс-оценка сложности алгоритма (+разбор задачи c Joker 2017 и DotNext 2017 Moscow)

Для любого практического применения log(n) можно считать константой. Просто в некоторых компаниях эта константа больше, чем у вас. © народная мудрость

Половину жизни я учу программировать. В том числе учу разработчиков делать быструю оценку вычислительной сложности алгоритма. Зачем?!

На первый взгляд, это довольно академический навык, который не нужен за рамками экзамена по алгоритмам. Однако опытные разработчики используют его ежедневно, не задумываясь, на уровне рефлексов. Делают они это для грубого анализа кода, который читают, пишут или только собираются написать. Обычно быстрого анализа асимптотики достаточно, чтобы исключить случайное появление сильно неэффективного кода.

Сначала разберёмся, как делать оценку сложности, на примере короткой, но нетривиальной задачи. Потом я расскажу, как научится делать экспресс-оценку, и покажу статистику о том, как решали задачу-пример участники конференций Joker и DotNext.

Картинка отсюда.

Задача на Joker 2017 и DotNext 2017 Moscow

Коллеги, которые были прошлой осенью на конференциях Joker в Питере и DotNext в Москве, попросили меня придумать какую-нибудь задачку про сложность для стенда Контура.

Сначала я решил, что сложность — плохая тема, скучная. Но всё таки решил попробовать, и по-моему в результате получилось довольно красиво! Идея родилась легко, по пути домой, а дальше я почти час за клавиатурой пытался оформить её в короткий, но эффектный кусочек кода на C#. Вот что получилось:

private static ISet<string> Compute(int n)
{
    var set = new HashSet<string>();

    for (int i = 2; i < n; i++)
        set.Add(ToBinaryString(i));

    for (int step = 2; step < n; step++)
        for (int i = 2 * step; i < n; i += step)
            set.Remove(ToBinaryString(i));

    return set;
}

private static string ToBinaryString(int x)
{
    return x == 0 ? "0" : ToBinaryString(x / 2) + x % 2;
}

То же код на Java

private static Set<String> compute(int n) {
    Set<String> set = new HashSet<>();

    for (int i = 2; i < n; i++)
        set.add(toBinaryString(i));

    for (int step = 2; step < n; step++)
        for (int i = 2 * step; i < n; i += step)
            set.remove(toBinaryString(i));

    return set;
}

private static String toBinaryString(int x) {
    return x == 0 ? "0" : toBinaryString(x / 2) + x % 2;
}

Предлагалось, изучив этот код, ответить на три вопроса:

• Что вообще делает этот странный код?
• Как можно его оптимизировать?
• Какая сложность у функции Compute(n)?

Наиболее точный ответ на последний вопрос предлагалось выбрать из внушительного списка вариантов:

• O(n)
• O(n²)
• O(n³)
• O(n log(n))
• O(n log²(n))
• O(n log³(n))
• O(n² log(n))
• O(n³ log(n))
• O(n² log²(n))
• O(n² log³(n))
• O(n³ log³(n))

Здесь самое время налить чашку кофе, прочитать фрагмент кода снова, порассуждать пять минут и выбрать ответ. Дальше будут спойлеры.

Решение

Начнём снизу вверх. Что делает метод ToBinaryString понять несложно — работая рекурсивно, он переводит строку в бинарную запись. Поскольку аргумент уменьшается вдвое на каждом вызове рекурсии, то её глубина — это O(log(x)). Поскольку ветвления рекурсии нет, то тут можно было бы и остановиться, решив, что сложность этой функции O(log(x)).

Но можно проявить чуть больше дотошности и вспомнить про неизменяемость строк в C# и Java. Действительно, конкатенация строк будет приводить к копированию, а значит работать будет за O(длина строки). А значит общая сложность будет чуть хуже логарифма. O(log²(x)) — наш выбор! Конечно, с практической точки зрения разница почти не заметна (см. эпиграф), но для задачки — самое то!

Вернёмся к методу Compute. Сложность первого цикла for — O(n log²(n)). Очевидно, сложность всего метода будет диктоваться более тяжёлыми вложенными for.

Внутренний цикл вложенных for будет делать O(n/step) вызовов ToBinaryString. Значит общая сложность будет O(n/2 + n/3 + n/4 +... n/(n-1)) = O(n(1/2 + 1/3 + ...))

Тут самое время совершить неглубокий нырок из компьютерных наук в матанализ, чтобы вспомнить, что формула в скобках — в точности частичная сумма гармонического ряда. Благо ряд этот изучен вдоль и поперёк. В частности, формула Эйлера сообщает нам, что частичные суммы растут как O(n log(n)). Спасибо, матанализ, пока-пока, до встречи! :)

А значит, вспомнив цену вызова ToBinaryString, оценить сложность нашего алгоритма сверху можно как O(n log³(n)). Это и есть ответ!

Получается, чтобы решить задачу, нужно довольно много:

• знать, что конкатенировать строки плохо
• уметь считать сложность рекурсивных методов
• знать, что remove у HashSet работает эффективно
• уметь сводить оценку сложности вложенных циклов к частичной сумме ряда
• и, наконец, знать про формулу Эйлера для частичной суммы гармонического ряда

Воу! Похоже, довольно круто получилось для такого маленького кусочка кода :)

Что вообще происходит?

Пора понять, что вообще делает этот странный код? Присмотритесь! Это же поиск списка простых чисел — методом недоделанного решета Эратосфена. Действительно, внутренний цикл удаляет каждое второе число, каждое третье и так далее. В итоге останутся только те, которые ни на что не делятся, кроме 1 и себя.

Тут не применены всем известные оптимизации (например, разумный выбор количества итераций циклов), а также добавлена пессимизация в виде ToBinaryString, чтобы совсем запутать. В итоге от исходной сложности O(n log(log(n))) и следа не осталось.

А вот некоторые интересные советы по оптимизации от участников конференций:

• Применить мемоизацию в ToBinaryString. Попросту говоря, кэшировать результат. Очевидно это ускорит работу, но совсем не очевидно, что это улучшит оценку сложности. А действительно улучшит. Как сильно — подумайте сами.
• Использовать не HashSet, а BitArray (C#) / BitSet (Java). Интересное предложение. Чтобы это сделать, придётся хранить в set не строки, а сами числа. А метод ToBinaryString применять только в конце к результату. Но уже один этот рефакторинг улучшит сложность. После этого замена коллекции, наверное, ускорит программу на константу, но на асимптотическую оценку сложности уже не повлияет :)
• Использовать другой алгоритм поиска простых чисел. Например, решето Аткина — за O(n / log(log(n))).

Участники Joker vs. участники DotNext

Статистика!

На Joker задачку решало 86 человек. Из них 8 дали верный ответ O(n log³(n)), а ещё 8 попались на уловку с конкатенацией и ответили O(n log²(n)).

На DotNext задачку решало 69 человек. Из них 10 ответили верно, а ещё 17 человек дали ответ O(n log²(n)). Но далеко идущих холиварных выводов о превосходстве дотнетчиков над джавистами по этой статистике сделать не получится. Мы точно знаем, что на DotNext приехали 49 контуровцев, и у них было преимущество.

Курс по оценке сложности за 2 часа

Вы ещё не забыли, что я учу программировать?

Прошлой осенью я запустил на ulearn.me, «нашей маленькой Курсере», миникурс по экспресс-оценке сложности алгоритмов. Его можно пройти всего за пару часов, он почти не содержит теории, зато придется решить 3 десятка задачек, ведущих вас от простых техник к более сложным. Если разбор этой задачи вам было понять сложновато — курс для вас.

Возможно, этот курс и повлиял на результаты. Тем более, что после Joker я добавил в него разбор элементов этой самой задачки — не пропадать же добру :)

Хотите потратить два часа, чтобы разобраться с экспресс-оценкой и не получить награду в нашей внутренней соцсети? Добро пожаловать на курс.

«Оценка сложности алгоритмов» на ulearn.me