Ограничения подсказывают сложность: бюджет операций

Если ты по ограничениям сразу видишь, какая сложность нужна, листай до «Теперь сам».

Как думаешь, что подойдёт

Задача: в списке до 200 000 чисел найти, сколько пар i < j дают сумму S. На ответ - 2 секунды, писать на Python. Подойдёт ли «каждый с каждым» - два вложенных цикла? Что нужно взамен?

Ответь себе до чтения. Два цикла - это n² / 2 = 2 · 10¹⁰ проверок. Ниже посчитаем, что машина успевает за две секунды, и окажется, что «каждый с каждым» закончит работу минут через пятнадцать.

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

Бюджет поездки. Есть 10 000 рублей и неделя. Перелёт за 40 000 не рассматривается вовсе, сколько ни ищи скидку, - это другой порядок. Поезд за 6 000 возможен, и дальше уже важны мелочи: купе или плацкарт, останется ли на еду. Ограничения задачи работают так же: сначала отсекают целые классы алгоритмов, потом внутри класса решает константа.

Механизм: бюджет, оценка, сравнение

Бюджет считают так: время на ответ умножают на скорость простых операций. Простая операция - одно сравнение, сложение, обращение к элементу списка; поиск в словаре - несколько таких (вычислить хеш, сравнить ключ), и его считают одной операцией с небольшой константой. Точность здесь - до порядка, не до единиц. Скорость своя у языка и машины, и её лучше знать замером, а не по памяти:

import random
import timeit

n = 10 ** 6


def slozheniya():
    s = 0
    for i in range(n):
        s = s + i
    return s


def slovar():
    d = {}
    for i in range(n):
        d[i] = i
    return d


a = [random.random() for _ in range(n)]


def sortirovka():
    return sorted(a)


for imya, f in [("сложение в цикле", slozheniya),
                ("запись в словарь", slovar),
                ("sorted, на элемент", sortirovka)]:
    t = min(timeit.repeat(f, number=1, repeat=5))
    print(f"{imya:20} {n / t / 1e6:6.1f} млн в секунду")

сложение в цикле       15.1 млн в секунду
запись в словарь        6.2 млн в секунду
sorted, на элемент      3.1 млн в секунду

Из пяти повторов берётся самый быстрый: медленнее его делают помехи - другие процессы, прерывания системы, - а не сама работа (раздел 25, честный замер). Строка sorted - это элементов в секунду: на каждый элемент сортировка делает около log₂ n ≈ 20 сравнений, но в коде на C. Для Python на этой машине рабочая цифра - порядка 10⁷ простых операций в секунду. У Лааксонена в «Guide to Competitive Programming» отправная точка для C++ - «несколько сотен миллионов простых операций в секунду». Разница в десятки раз - цена интерпретатора.

Дальше в оценку алгоритма подставляют наибольшее n из условия и сравнивают с бюджетом. Удобнее заранее знать обратное: какое наибольшее n проходит при данной сложности. Это считается программой:

import math

def lin(n):
    return n

def nlogn(n):
    return n * math.log2(n)

def kvadrat(n):
    return n * n

def kub(n):
    return n * n * n

def eksp(n):
    return 2 ** n * n

def faktorial(n):
    return math.factorial(n)

def predel(f, byudzhet):
    # самое большое n, при котором f(n) <= byudzhet:
    # удвоение, потом пополам
    hi = 2
    while f(hi) <= byudzhet:
        hi = hi * 2
    lo = hi // 2
    while hi - lo > 1:
        mid = (lo + hi) // 2
        if f(mid) <= byudzhet:
            lo = mid
        else:
            hi = mid
    return lo

print("сложность: n при бюджете 10^7 | 10^9")
for imya, f in [["n", lin], ["n log n", nlogn], ["n^2", kvadrat],
                ["n^3", kub], ["2^n * n", eksp], ["n!", faktorial]]:
    print(imya + ":", predel(f, 10 ** 7), "|", predel(f, 10 ** 9))

сложность: n при бюджете 10^7 | 10^9
n: 10000000 | 1000000000
n log n: 526172 | 39620077
n^2: 3162 | 31622
n^3: 215 | 1000
2^n * n: 19 | 25
n!: 10 | 12

Заметь, как по-разному строки отзываются на стократный рост бюджета. Линейная граница выросла в сто раз, квадратичная - в десять (√100), кубическая - в 4,6 (∛100), экспоненциальная - на шесть единиц, а факториальная - на две. Чем круче рост, тем меньше помогает железо: быстрая машина почти ничего не даёт экспоненте.

Правило

Бюджет = время × скорость простых операций (Python - порядка 10⁷ в секунду, компилируемый код - 10⁸-10⁹). Подставь наибольшее n в оценку: если вышло больше бюджета в десятки раз и больше - класс не годится, ищи другой. Если в пределах нескольких раз - решит константа, и это проверяется замером. Маленькие ограничения (n ≤ 20) - тоже подсказка: подмножеств 2²⁰ ≈ 10⁶, и даже с работой n на каждое выходит 2 · 10⁷ - в бюджете. Автор задачи разрешает перебор.

Разбор: 200 000 чисел за две секунды

Вернёмся к задаче из начала. Бюджет на Python: 2 с × 1,5 · 10⁷ ≈ 3 · 10⁷ операций.

Квадрат отпадает сразу - никакая оптимизация внутреннего цикла не вытащит семьсот раз. Одна деталь, если идти двумя указателями: задача считает пары позиций, а равные числа встречаются много раз. Когда сумма совпала, указатели обрабатывают сразу блоки равных значений: k одинаковых слева и m справа дают k · m пар, а если b[i] = b[j] - C(k, 2) пар внутри блока. Сдвиг по одному элементу эти пары потеряет - поэтому словарь счётчиков из прошлого урока здесь проще. Оба остальных проходят, и запас у n log n в девять раз как раз покрывает то, что одна «операция» сортировки - это сравнение и перестановка, а не одно сложение. По таблице из механизма видно то же самое: n = 2 · 10⁵ стоит между строкой n log n (526 172) и строкой n² (3162).

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

Разбор: одинаковая асимптотика, разница в двадцать раз

Таблица говорит о классах, но не о константах. Сравним две сортировки за n log n на тех же 200 000 числах: встроенную sorted и честное слияние на Python.

import random
import timeit

random.seed(1)
n = 200000
a = [random.random() for _ in range(n)]


def sliyaniem(a):
    # сортировка слиянием на чистом Python: тот же n log n, что у sorted
    if len(a) <= 1:
        return a
    m = len(a) // 2
    l, r = sliyaniem(a[:m]), sliyaniem(a[m:])
    out, i, j = [], 0, 0
    while i < len(l) and j < len(r):
        if l[i] <= r[j]:
            out.append(l[i])
            i += 1
        else:
            out.append(r[j])
            j += 1
    return out + l[i:] + r[j:]


def kvadrat(a):
    # пары «каждый с каждым» на 2000 элементах - кусок от n² для оценки;
    # x < y - одно сравнение; в задаче ещё и сложение, так что
    # настоящий перебор не быстрее: оценка снизу
    s = 0
    for x in a[:2000]:
        for y in a[:2000]:
            if x < y:
                s += 1
    return s


t_sorted = min(timeit.repeat(lambda: sorted(a), number=1, repeat=5))
t_merge = min(timeit.repeat(lambda: sliyaniem(a), number=1, repeat=3))
t_kv = min(timeit.repeat(lambda: kvadrat(a), number=1, repeat=3))
raz = t_merge / t_sorted
t_n2 = t_kv / 2000 ** 2 * n * n
print(f"sorted:            {t_sorted * 1000:6.0f} мс")
print(f"слиянием в Python: {t_merge * 1000:6.0f} мс,"
      f" в {raz:.0f} раз дольше")
print(f"n² для n = {n}: {t_n2:6.0f} с (по замеру на 2000)")

sorted:                47 мс
слиянием в Python:    940 мс, в 20 раз дольше
n² для n = 200000:   1640 с (по замеру на 2000)

Обе сортировки - n log n, а между ними двадцать раз: sorted написана на C, а слияние на Python платит интерпретатором за каждое сравнение. Квадрат - n² сравнений пар, как в замере на 2000 элементах, - это 1640 секунд (половина пар, i < j, - около 820). Это оценка снизу: в замере одно сравнение на пару, а в задаче ещё и сложение. Даже она в сотни раз хуже медленной сортировки. Это и есть граница правила: таблица отличает класс от класса (тысячи раз), но не решает спор внутри класса (десятки раз). Слияние на Python укладывается в две секунды с запасом вдвое - но если бы ограничение было 0,5 секунды, прошла бы только sorted.

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

Решение, которое не может пройти. Час на аккуратный квадратичный код, потом «превышено время» на большом тесте - и всё заново.

Оптимизация не того. Ускорить внутренний цикл квадрата вдвое - бессмысленно, если не хватает в тысячу раз.

Пропущенная подсказка. Ограничение n ≤ 20 проглядели и искали полиномиальный алгоритм для NP-трудной задачи, хотя автор прямо разрешил перебор 2ⁿ.

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

В работе ограничений никто не пишет - их узнают. «Сколько заказов в день сейчас и сколько будет через год?» - это n. «Отчёт строится ночью или по кнопке, пока человек ждёт?» - это время. Две цифры и таблица из этого урока за минуту говорят, хватит ли сортировки или нужен индекс, и можно ли позволить себе перебор. Если данные растут, показатель роста меряют опытом с удвоением из раздела 25.

Теперь сам

1. n ≤ 5000, одна секунда, Python. Пройдёт ли n² с простым телом цикла? А в C++?
2. В условии n ≤ 15 и нужно перебрать все подмножества, на каждое тратя O(n). Сколько это операций?
3. Сколько примерно займёт sorted на 10⁶ случайных чисел на этой машине?