Раздел I · постановка вопроса

Два решения одной задачи

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

64 против 6; при n = 1024 — 1024 против 10. Различие устойчиво и растёт с размером входа. Задача раздела — построить меру, которая описывает это различие независимо от вычислительной машины.

Раздел I · первый вариант меры

Секунды описывают запуск, а не алгоритм

Одна и та же программа на одних и тех же данных даёт разное время на разных запусках и на разных машинах.

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

Раздел II · что считать за единицу

Элементарная операция

Элементарная операция — действие, время выполнения которого не зависит от размера входных данных. Такое действие принимают за единицу счёта.

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

Раздел II · две строки рядом

Одинаковые по виду, разные по стоимости

Обе строки проверяют, встречался ли номер раньше. Написаны они почти одинаково, а работы выполняют разное количество.

seen = set()
...
if badge in seen:

seen = []
...
if badge in seen:

Разница в одной записи — set() вместо [] — меняет стоимость строки с 1 на n. Это самая частая причина, по которой решение получает верный ответ, но не проходит по времени.

Раздел II · между единицей и n · часть 1

Дешевле полного прохода и дороже его

Список из 1000 номеров. Полный проход по нему стоит 1000 действий. Первая строка справляется за 10, вторая тратит 10 000 — и обе записаны в одну строку кода.

from bisect import bisect_left   # стандартный модуль

i = bisect_left(codes, 480)     # 10 действий
# то же половинным делением вручную:
while low <= high:
    mid = (low + high) // 2
    if codes[mid] < 480:
        low = mid + 1
    else:
        high = mid - 1

prices.sort()                   # ≈10 000 действий
sorted(prices)[:3]              # столько же
min(prices)                     # 1000 действий

Раздел II · между единицей и n · часть 2

Когда стоимость определяется не длиной списка

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

window = prices[10:20]
first_ten = text[:10]

if "отказ" in log_line:
    ...
big_list + other_list

orders.append(x)
orders.pop()

Итого стоимость строки бывает четырёх видов. 1 — не зависит от данных; log n — данные делятся пополам; n и выше — данные просматриваются целиком; k или m — работу задаёт отдельная величина. Все четыре встретятся при разметке фрагментов.

Раздел II · одна операция, разные структуры

Стоимость зависит не от действия, а от структуры данных

Одно и то же действие стоит по-разному в списке, множестве, словаре и очереди. Выбор структуры — основной способ изменить сложность решения.

Отсюда практическое правило, к которому мы вернёмся в разделе о памяти. Если решение упирается в проверку наличия — берут множество; если в добавление и снятие с обоих концов — deque; если нужен доступ по номеру — список. Замена структуры меняет класс сложности, не меняя логики решения.

Раздел II · на чём держится счёт

Три допущения, которые мы принимаем

Считая обращение к памяти за единицу, мы пользуемся упрощённой моделью машины. В анализе алгоритмов она называется RAM — машина с произвольным доступом к памяти.

Модель сознательно огрубляет устройство машины — иначе оценка зависела бы от конкретного процессора. Чем приходится платить за это упрощение, разбирается в разделе VIII.

Раздел II · вторая величина

Размер входа n

Размер входа n — та характеристика данных, при росте которой растёт объём работы. Прежде чем считать операции, нужно назвать, что именно в задаче является n.

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

Пример 4 из 5 · откуда берётся n²

Почему 28 сравнений — это n², а не n

Число сравнений равно n(n−1)/2 — половине квадрата. Проверим по определению класса: посмотрим, как оно меняется, когда вход удваивается.

Раздел III · пять примеров рядом

Как ведут себя пять функций T(n)

Примеры ② и ③ различаются вдвое по числу операций, но ведут себя одинаково. Примеры ④ и ⑤ различаются всего на 8 операций при n = 8 — и тоже ведут себя одинаково. Функции разбиваются на группы по тому, как они ведут себя при росте n. Эти группы и записывает O-нотация.

Раздел IV · результат упрощения

Пять функций — два класса

Применим оба правила к пяти примерам, которые считали построчно. Пять разных формул превращаются в три записи, а из них две совпадают.

Примеры ② и ③ получили одну запись. Точность при этом не теряется: они действительно ведут себя одинаково. Примеры ④ и ⑤ тоже совпали, хотя один написан с вложенным циклом, а другой без него.

Раздел IV · строгое определение

Что означает запись O(f(n))

Обозначение пришло из математического анализа: символ ввёл Пауль Бахман в 1894 году, в анализ алгоритмов его перенёс Дональд Кнут в 1976-м. Отсюда и свойство записи — она описывает поведение функции при больших n.

Раздел IV · применение определения

Проверим: 4n + 5 действительно O(n)

Чтобы доказать оценку, достаточно предъявить одну пару чисел (c, n₀), при которой неравенство выполняется. Возьмём пример ③ и найдём такую пару.

Раздел IV · правила действий с оценками

Три свойства, которыми пользуются при анализе

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

Раздел V · каталог

Классы сложности в порядке возрастания

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

Класс 1 из 6 · примеры

Где встречается константная сложность

orders[0]
orders[-1]
prices[i]

if badge in seen:
    ...
counts[word] = 0

len(orders)
orders.append(x)

Признак класса: отсутствие цикла по входным данным и отсутствие вызовов, содержащих такой цикл. Второе условие существеннее первого — раздел VI.

Класс 2 из 6 · примеры

Где встречается логарифмическая сложность

while low <= high:
    middle = (low + high) // 2
    if ids[middle] < target:
        low = middle + 1
    else:
        high = middle - 1

result = 1
while power > 0:
    if power % 2:
        result *= base
    base *= base
    power //= 2

low, high = 1, 1000
while low <= high:
    guess = (low + high) // 2
    if guess < secret:
        low = guess + 1
    else:
        high = guess - 1

Признак класса: управляющая величина делится, а не уменьшается на единицу. Сравните: i //= 2 даёт log n итераций, i -= 1 — n итераций.

Класс 3 из 6 · примеры

Где встречается линейная сложность

total = 0
for value in temperatures:
    total += value

counts = {}
for word in words:
    counts[word] = counts.get(word, 0) + 1

i = j = 0
while i < len(left) and j < len(right):
    if left[i] <= right[j]: i += 1
    else: j += 1

Признак класса: один проход по входу, тело которого выполняется за постоянное время. Несколько последовательных проходов класс не меняют: n + n + n = 3n = O(n).

Класс 4 из 6 · примеры

Где встречается линейно-логарифмическая сложность

prices.sort()
sorted(prices)[:3]

orders.sort()
for i in range(1, len(orders)):
    if orders[i] == orders[i - 1]:
        return True

def kth_largest(prices, k):
    return sorted(prices, reverse=True)[k - 1]

Признак класса: сортировка в решении либо рекурсивное деление задачи пополам с линейным объединением. Наличие sorted() само по себе задаёт нижнюю границу класса — быстрее решение уже не будет.

Класс 5 из 6 · примеры

Где встречается квадратичная сложность

for i in range(len(points)):
    for j in range(i + 1, len(points)):
        distance(points[i], points[j])

for i in range(1, len(data)):
    j = i
    while j > 0 and data[j-1] > data[j]:
        data[j-1], data[j] = data[j], data[j-1]
        j -= 1

for row in rows:
    if row not in result:
        result.append(row)

Признак класса: вложенные циклы по одному входу либо операция стоимостью O(n) внутри цикла по входу. Если внутренний цикл идёт по другой величине m, оценка равна O(n·m).

Раздел V · сравнение на одной задаче

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

Определить, есть ли в списке два одинаковых номера. Слева — проход с множеством просмотренных значений, справа — перебор всех пар.

Раздел V · числовые значения

Порядок роста в числах операций

Столбец n = 10 показывает, почему оценка не применяется к малым входам: различие между 33 и 100 операциями несущественно. Столбец n = 10⁶ показывает обратное: при том же алгоритме различие между O(n log n) и O(n²) достигает пяти порядков. На этом экране заканчивается первая пара.

Раздел VI · зависимость от данных

Лучший, средний и худший случай

На входах одного размера алгоритм может выполнять разное число операций. Линейный поиск прекращает работу при первом совпадении, поэтому T(n) — не одна функция, а три.

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

Раздел VII · память · примеры

Сколько памяти у знакомых решений

Четыре функции, которые уже разбирались. Время у них разное, а память определяется одним: завели новую структуру или обошлись переменными.

def count_late(orders):
    late = 0
    for order in orders:
        if order.delay > 0:
            late += 1
    return late

def has_pair(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return True
    return False

def has_duplicate(badges):
    seen = set()
    for badge in badges:
        if badge in seen:
            return True
        seen.add(badge)
    return False

def top_three(prices):
    return sorted(prices)[:3]

Правило для разметки: завели множество, словарь, копию или результат sorted() — это O(n) памяти; обошлись счётчиками и индексами — O(1). Промежуточных случаев на этом занятии не встретится.

Раздел VIII · границы метода

Два случая, когда оценка не отвечает на вопрос

Оценка говорит, что будет при большом n. Есть две ситуации, где этого недостаточно, и решение выбирают не по ней.

Оценку называют всегда: она отсекает заведомо неподходящие решения до написания кода. Но если размер данных известен и невелик, выбирают замером. Оценка отвечает на вопрос «что будет, когда данных станет много», замер — «что быстрее вот на этих данных». Замерами занимаемся на занятии 4.

Раздел IX · применение

Ограничение входа определяет допустимый класс

Обратная задача анализа: по ограничению из условия определить, какие решения имеют шанс уложиться в лимит времени. Ориентир для Python — 10⁷ элементарных операций в секунду; величина приблизительная и зависит от машины и содержимого цикла.

Последняя строка: при n ≤ 10⁹ один проход по входу требует около двух минут — значит, исключён самим ограничением. Если при этом на входе одно число, а не список, ответ получают формулой либо делением пополам.

Раздел IX · рабочий порядок

Последовательность анализа незнакомого кода

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

Карточки · набор А · разбор

Ответы с подсчётом

Разбор А3 и А5 рядом показывает главное различие: в А3 циклы идут подряд и стоимости складываются, в А5 проход спрятан внутри строки и стоимости перемножаются.

Карточки · набор Б · разбор

Ответы с подсчётом

Три ответа из шести содержат то, о чём чаще всего забывают: Б1 — память под результат sorted(), Б2 и Б5 — вторую величину в оценке, Б4 — память под стек рекурсии. Именно эти три пункта проверяются на приёмке.

Справка · материал занятия в сжатом виде

Сводка

Форма ответа: «Время O(?), поскольку подсчитанные операции. Память O(?): хранится что. Худший случай — входные данные. Альтернатива — вариант и причина отказа».

Справка · распространённые ошибки

Шесть неверных утверждений

Домашнее задание № 2 · задание 2 · как именно работать с моделью

Модель отвечает, разбираетесь вы

Второе задание — единственное, где ИИ разрешён прямо и намеренно. Задача — научиться проверять чужую оценку: то же самое вы делаете на review и на секции, когда решение предлагает кто-то другой.

Домашнее задание № 2 · порядок сдачи

Куда положить и как сдать

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