Алгоритмы на каждый день: быстрые способы оценивать сложность без формул

В теории алгоритмов принято начинать с асимптотики: O(n), O(n log n), O(n^2) и так далее. Но в реальной разработке и на собеседованиях часто важнее другое: быстро понять, почему алгоритм будет медленным, какие именно операции доминируют, и какую структуру данных стоит выбрать вместо “очевидного” варианта.

Хорошая новость: оценивать сложность можно без формул. Точнее — без длинных математических вывода. Достаточно научиться распознавать тип входных данных, смотреть на форму циклов и проверок, понимать стоимость базовых операций и выбирать структуру данных под “характер” задачи. В этой статье разберём именно такие “интуитивные” техники — на тех паттернах, которые встречаются каждый день.

Как думать о сложности без формул

Отталкиваемся от входных данных, а не от кода “в вакууме”

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

Асимптотика — это про поведение при росте n. Но n должно быть осмысленным параметром:

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

Например, в задаче “найти элемент в массиве” n — длина массива, а вот в задаче “посчитать частоты” важнее соотношение n и количества уникальных значений k.

Интуитивное правило: сначала определить, что именно растёт и что может быть “специфично” для данных (уникальность, упорядоченность, плотность, средняя длина подзадач).

Считаем не “в уме”, а “по доминирующему месту”

Вместо строгого подсчёта удобно задавать вопрос:

Какая операция повторяется чаще всего и как она растёт вместе с входом?

Обычно один участок кода и является доминирующим:

• вложенные циклы,
• перебор по структуре данных внутри другого перебора,
• сортировка как “узкое горлышко”,
• повторные сканирования одного и того же набора данных.

Интуитивное правило: если есть вложенность по одному и тому же параметру n, сложность почти всегда будет как минимум квадратичной или хуже.

Тип входных данных как “компас”

Ниже — практические признаки входных данных, которые напрямую подсказывают структуру данных и прогноз по сложности.

1) “Линейный” ввод: массив/список без дополнительных свойств

Сигнал: нет сортировки, нет гарантий о повторяемости, доступ только через индекс или через итерацию.

Что обычно можно ожидать:

• один проход по массиву: “почти всегда” O(n),
• поиск по условию без индексации: “скорее всего” O(n) на один запрос,
• если поиск делается внутри цикла — возможен O(n^2).

Что делать: если нужно многократно отвечать на запросы по значениям — думать про индексирование (словарь/хэш-таблица).

2) Много запросов на одном и том же наборе данных

Сигнал: “дан список, затем q запросов” — классика.

Тут интуитивная стратегия:

• если на каждый запрос сканировать весь список — легко получить O(nq),
• если предварительно построить структуру (частоты, индексы, словарь значений, таблицу переходов) — стоимость часто смещается в “один раз” и затем уменьшается на каждом запросе.

Пример: “для каждого числа сказать, встречалось ли оно раньше”.
Наивно: для каждого элемента проверять предыдущие — квадратично.
Быстро: завести set и проверять за константное время.

3) Наличие упорядоченности

Сигнал: данные отсортированы, или есть возможность сортировать заранее.

Интуитивно:

• линейный проход по отсортированному массиву иногда заменяет более дорогие проверки,
• бинарный поиск работает как “уменьшение глубины” в логарифм.

Хотя формул в статье мы избегаем, полезная мысль остаётся:

упорядоченность позволяет заменить “поиск перебором” на “поиск разбиением”.

4) Ограниченная “сфера значений”: маленький диапазон

Сигнал: значения в [0..M) или диапазон маленький относительно n.

Интуитивный ход:

• счётчики/частотные массивы дают ускорение и предсказуемость,
• иногда можно заменить хэш-таблицы на массивы частот.

Подводный камень: если диапазон огромный, массивы частот могут съесть память — и “выигрыш по времени” превращается в проблему по ресурсам.

5) Графы и “число связей”

Сигнал: граф, матрица смежности, список смежности.

Тут важнее различать:

• количество вершин V,
• количество рёбер E.

Интуитивная оценка:

• алгоритмы по матрице часто “зависят” от V^2,
• по спискам смежности — обычно зависят от V + E.

Правило: когда вход — граф, параметр сложности не один, и “скорость” часто определяется именно числом связей.

Быстрые методы оценивания по форме кода

Вложенные циклы — главный источник “взрывной” сложности

Посмотрите на структуру:

Паттерн A: Один цикл

for x in arr:
    if condition(x):
        ...

Скорее всего, время линейное по числу элементов.
Даже если внутри условие сложнее, оно обычно “константное” по n.

Паттерн B: Два вложенных цикла по одному и тому же массиву

for i in range(n):
    for j in range(n):
        check(arr[i], arr[j])

Интуитивно: каждое значение сравнивается со всеми — квадратичный рост почти неизбежен.
Если внутри ещё и линейная операция — это уже “тройной” уровень.

Паттерн C: Вложенность, но внутренний цикл зависит от внешнего

for i in range(n):
    for j in range(i, n):
        check(arr[i], arr[j])

Здесь тоже рост “примерно как квадрат”, но с меньшим коэффициентом. Важно то, что параметр тот же — пары элементов.

Подводный камень: иногда “кажется, что в сумме меньше”, но асимптотика часто всё равно остаётся той же при больших n.

Сканирование внутри цикла: ошибка №1 в реальных задачах

Самая распространённая причина случайно получить O(n^2):

• внешний цикл по данным,
• внутри — поиск/сканирование по этому же набору.

Например: найти для каждого элемента все индексы в списке, где он встречается.

Наивный вариант:

def indices_naive(arr, value):
    res = []
    for i, x in enumerate(arr):
        if x == value:
            res.append(i)
    return res

def positions_for_all_values(arr):
    out = {}
    for x in arr:  # внешний цикл по элементам
        out.setdefault(x, indices_naive(arr, x))  # внутри сканирование arr
    return out

Если все значения уникальны, то indices_naive(arr, x) вызывается n раз и каждый раз сканирует n элементов. Это даёт квадратичный рост.

Интуитивная диагностика: “мы снова и снова пробегаем по одним и тем же данным”.
Лечение: строим индекс один раз (словарь частот/списки индексов).

Оптимизация:

from collections import defaultdict

def positions_for_all_values(arr):
    out = defaultdict(list)
    for i, x in enumerate(arr):
        out[x].append(i)
    return dict(out)

Теперь один проход по массиву: время порядка линейного (и память — тоже).

Структуры данных как ответ на вопрос “что мы делаем с данными”

Словарь (dict) и множество (set): быстрый способ уйти от квадратичности

Эти структуры “оптимизируют” паттерн “найти по ключу” или “проверить наличие”.

Интуитивное соответствие:

• если задача сводится к “часто спрашиваем: есть ли это значение?” → set,
• если “нужно хранить агрегат по значению” (частоты, сумма, последний индекс) → dict.

Пример: “для каждого элемента определить, встречалось ли оно ранее”.

Наивно: сканировать префикс.

def exists_before_naive(arr):
    res = []
    for i, x in enumerate(arr):
        ok = False
        for j in range(i):
            if arr[j] == x:
                ok = True
                break
        res.append(ok)
    return res

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

Быстро:

def exists_before(arr):
    seen = set()
    res = []
    for x in arr:
        res.append(x in seen)
        seen.add(x)
    return res

Смысл без формул: мы перестали “пересчитывать префикс заново” и начали хранить результат предыдущих вычислений.

Очереди и стеки: распознаём “локальную причинность”

Для задач на проход по структурам часто важны не только асимптотики, но и корректность.

• стек (LIFO) — естественен для DFS (глубинного обхода),
• очередь (FIFO) — естественна для BFS (обход по слоям).

Сложность обычно выходит “линейной относительно размера графа/структуры”, если вы не добавляете один и тот же узел многократно.

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

Сортировка: полезный “переключатель режимов”

Сортировка часто переводит задачу из режима “сложно сравнивать напрямую” в режим “можно проходить и проверять локальные условия”.

Но есть нюанс: сортировка — это не “бесплатно”. Интуитивно:

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

Хороший тест:

Если сортировать, получим ли мы структуру, на которую дальше можно опереться так, чтобы перестать делать дорогие проверки?

Пример: “найти пары с суммой, равной X” в массиве.

• Наивно: двойной перебор — квадратично.
• Оптимально: отсортировать и использовать два указателя — избегаем вложенности.

Интуитивные оценки сложности на реальных сценариях

Сценарий 1: “Сделать для каждого элемента что-то, требующее другого поиска”

Классический вопрос: “Найти ближайший больший/меньший”, “сопоставить элементы по условию”, “подобрать пары”.

Если вы начинаете с вложенных циклов — остановитесь.
Почти всегда есть путь через:

• индексирование (dict/set),
• двухуказательную технику после сортировки,
• монотонный стек (для “ближайших” условий),
• предварительные вычисления (prefix/suffix).

Монотонный стек — пример структуры, которая часто “магически” сокращает время. Но магии нет: она превращает много повторных сравнений в “каждый элемент обрабатывается ограниченное число раз”.

Интуитивное правило для таких структур:

Если вы видите, что элемент “может быть отброшен” и больше не возвращается — значит, у вас амортизированная (в сумме) эффективность.

Сценарий 2: “Срезы/подстроки в строках”

Строки в Python — особый случай: операции могут быть не такими “константными”, как кажется.

Интуитивно:

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

Реальная практика: когда вход — строка длины n, неочевидные подоперации часто дают множитель n.

Что делать:

• стараться избегать построения новых больших строк в цикле,
• использовать списки символов и ''.join(),
• для задач поиска подстрок — думать о алгоритмах уровня KMP/rolling hash, но это тема отдельной большой статьи.

Сценарий 3: “Частоты, пересечения, уникальные элементы”

Здесь успех почти всегда равен правильному выбору структуры.

• Частоты: collections.Counter или обычный dict.
• Пересечение множеств: set(a) & set(b) — работает через свойства хэширования.
• Уникальные элементы: set(arr).

Наивные подходы обычно включают:

• вложенные циклы,
• проверку “не встречалось ли раньше” через сканирование.

Интуитивная диагностика: если вы для каждого элемента проверяете “первую встречаемость” через поиск в списке — это верный путь к квадратичности.

Сценарий 4: “Динамика: DP без понимания размеров состояния”

DP легко довести до неуправляемого объёма памяти/времени.

Интуитивная проверка:

• какие измерения у таблицы?
• что будет, если размеры состояния растут до максимумов?
• можно ли сжать состояние (rolling array), если переход зависит только от соседних слоёв?

Пример: dp[i][j] — это квадрат от размеров, если i и j масштабируются вместе. Если вы сомневаетесь, проще оценить:

сколько значений состояний в худшем случае вы храните?

С памятью это обычно “пробивает” раньше времени.

Частые ошибки в интуитивных оценках

Ошибка 1: игнорировать стоимость базовых операций

Даже если алгоритм “вроде бы один цикл”, но внутри вы выполняете операцию, которая сама сканирует структуру.

Например, списки:

• x in list — линейное по длине списка,
• list.remove(x) — тоже линейное.

Поэтому:

• частые проверки наличия → set,
• частые индексы по ключу → dict.

Ошибка 2: путать n и “сколько реально повторяется”

Если вход содержит много повторов, то итоговая сложность может зависеть от k (количество уникальных значений), а не от n.

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

Ошибка 3: недооценивать худший случай хэш-структур

В Python dict и set в среднем работают быстро, но теоретически возможны худшие сценарии. На практике для большинства задач это оправдано, и именно поэтому хэш-структуры часто являются рациональным выбором “без формул”.

Практическая “шпаргалка” для быстрой оценки

Перед тем как написать оптимальный алгоритм, удобно пройти короткий чеклист.

Шаг 1: что такое n в задаче?

• длина массива/строки?
• количество вершин?
• количество запросов?

Шаг 2: сколько раз мы “сканируем” вход?

• один проход,
• несколько проходов,
• сканирование внутри каждого запроса,
• сканирование внутри внутреннего цикла.

Шаг 3: какие операции внутри цикла?

• доступ по индексу в массиве,
• поиск in в списке,
• поиск по ключу в словаре/множестве,
• конкатенация строк,
• сортировка.

Шаг 4: есть ли признаки упорядоченности/малого диапазона/повторов?

Это определяет, можем ли мы:

• заменить перебор на индексирование,
• уйти от квадратичности через предварительную обработку,
• заменить структуры на более дешёвые.

Небольшой пример “интуитивного” анализа на Python

Допустим, задача: “дан список arr, нужно для каждого элемента посчитать количество его вхождений”.

Наивное решение:

def counts_naive(arr):
    res = []
    for x in arr:
        c = 0
        for y in arr:
            if y == x:
                c += 1
        res.append(c)
    return res

Интуитивная оценка:

• внешний цикл по n,
• внутренний цикл тоже по n,
• сравнение — константно.
  Итого: примерно квадрат по n.

Оптимальное:

from collections import Counter

def counts_fast(arr):
    freq = Counter(arr)  # один проход
    return [freq[x] for x in arr]  # снова проход

По сути:

• мы перестали повторно считать частоты для каждого элемента;
• частоты посчитали один раз и дальше сделали обращение по ключу.

Вывод: сложность — это навык выбора режимов

Оценивать сложность “без формул” — это не отказ от математики, а другой уровень наблюдательности. Вы начинаете видеть алгоритм