Оценка сложности: почему решение не проходит

Вы уже сталкивались с вердиктом «превышено время» и знаете первое правило: перемножить длины циклов и сравнить с десятью миллионами. Пришло время разобраться, откуда взялось это число и что делать, когда его не хватает.

Ориентир простой. За одну секунду Python успевает порядка $10^7$ простых операций. Компилируемые языки — примерно в тридцать раз больше, около $3 \cdot 10^8$.

Простая операция — это одно сравнение, одно сложение, одно обращение к элементу списка. Не вызов метода, который сам пробегает по данным, — об этом отдельно.

Отсюда получается таблица, которую полезно помнить наизусть:

Обратите внимание: разница между «проходит» и «не проходит» — это не разница в аккуратности кода. Это разница в количестве шагов, то есть в самом подходе.

Точное количество операций никого не интересует — важен порядок роста: как меняется работа, когда данных становится вдвое больше.

Записывают это буквой $O$ и оставляют только главное: константы и младшие слагаемые отбрасывают.

Почему отбрасывают константы: разница между $2n$ и $5n$ — это разница в разы, а между $n$ и $n^2$ при ста тысячах — в сто тысяч раз. Второе решает судьбу решения, первое почти никогда.

Отдельно про $O(n \log n)$: множитель $\log n$ — это примерно 17 при $n = 100\,000$ и 20 при миллионе. То есть сортировка дороже одного прохода в двадцать раз, а квадрат — в сто тысяч. Между ними пропасть, и сортировки бояться не нужно.

В задаче $n$ до $10^5$, и решение перебирает все пары элементов.

Что будет?

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

Читать эту таблицу нужно до того, как писать код. Увидев $n$ до двухсот тысяч, вы сразу знаете: перебора пар не будет, нужен словарь, множество или сортировка.

И наоборот: если в условии $n$ до двух тысяч, а вы придумали хитрое линейное решение — скорее всего, вы усложняете. Квадрат там разрешён специально.

Маленькое ограничение — это разрешение, а не ловушка. Оно говорит: «тут можно в лоб».

Два обстоятельства, из-за которых оценка «на глаз» в Python обманывает.

Первое: цикл дорог, а встроенное дёшево. Метод sort, функция sum, проверка in для множества написаны на C и работают в десятки раз быстрее того же самого, набранного циклом. Поэтому sum(a) предпочтительнее ручного накопления — не ради красоты, а ради скорости.

Второе: стоимость строки не видна. Вот примеры, где одна короткая запись стоит целого прохода:

Каждая из них внутри цикла превращает $O(n)$ в $O(n^2)$ — незаметно, потому что вложенности в тексте нет.

Проверка простая: если внутри цикла стоит что-то, что само проходит по данным, сложность умножается. Именно так решение из шести аккуратных строк получает превышение времени.

Решение работало за $O(n)$ и укладывалось в секунду при $n = 10^6$.

Во сколько примерно раз дольше будет работать решение за $O(n^2)$ при том же $n$? Введите степень десяти — то есть если ответ «в миллион раз», введите 6.

Оценка по виду кода, а не по смыслу. Шесть строк могут работать дольше, чем тридцать. Считать надо шаги, а не строки.

Забытая стоимость встроенного. count, index, in по списку, срезы — всё это проходы. Внутри цикла они дают квадрат.

Оптимизация не того. Когда сложность неверна, мелкие улучшения бесполезны: ускорение в два раза не спасёт решение, которому не хватает тысячекратного. Сначала меняют подход, потом уже отлаживают мелочи.

Как проверять себя

• посмотрите на ограничения и назовите ожидаемую сложность до написания кода;
• найдите самый вложенный цикл и посчитайте, сколько раз выполнится его тело;
• проверьте, нет ли внутри скрытого прохода — метода или среза;
• перемножьте и сравните с таблицей.

Лестница прежняя: пять разминочных, семь основных, три со звёздочкой. Зачёт при десяти решённых.

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

Поэтому порядок работы такой: сначала прочитать ограничение, назвать нужную сложность, и только потом выбирать средство. В нескольких задачах ограничение, наоборот, маленькое — там квадрат разрешён, и усложнять не надо.

Для задачи «дан список из $n$ чисел, найдите количество пар элементов с равными значениями» написали три решения. Ограничение: $n$ до $2 \cdot 10^5$.

Первое

count = 0
for i in range(len(a)):
    for j in range(i + 1, len(a)):
        if a[i] == a[j]:
            count += 1

Второе

count = 0
for value in set(a):
    c = a.count(value)
    count += c * (c - 1) // 2

Третье

counts = {}
for value in a:
    counts[value] = counts.get(value, 0) + 1
count = 0
for key in counts:
    c = counts[key]
    count += c * (c - 1) // 2

Все три считают правильно. Оцените сложность каждого, скажите, какие пройдут по времени, и объясните, почему второе решение опаснее, чем кажется.