---
title: Сложность алгоритмов — методичка (время, память, граничные случаи)
source: подготовлено 2026-09-12, основание — TASK-43 (инфраструктура экзаменации) и TASK-11 (формат разборов)
---

# Сложность: время, память, граничные случаи

Методичка под формат ответа, зафиксированный в `README.md`: **идея + структура данных + сложность + граничные случаи**. По итогам раундов 1–2 идеи верны во всех 32 задачах, но в ответах ни разу не названы время, память и граничные случаи вместе — это единственный оставшийся разрыв до оценки 3. Документ закрывает именно его.

**Как пользоваться:**
1. Прочитать блоки 1–8 один раз — это база.
2. Перед каждым билетом вслух проговаривать три блока из §11 (время / память / границы), даже если задача элементарная.
3. Таблица §10 — эталон для самопроверки после разбора: сверить названные числа с каноном.
4. §12 — приоритеты на тренировку.

---

## 1. Как это звучит на интервью

Интервьюер ждёт не одну цифру, а **полное предложение**:

> «Время **O(n log n)** — доминирует сортировка, остальное линейно. Память: **O(n)** дополнительная на слияние и **O(log n)** стек рекурсии; результат строю отдельным массивом, вход не меняю. Худший случай: ...»

Что почти всегда забывают назвать:

1. **Что такое n.** Всегда объявлять переменную: «n — число элементов, k — размер окна, N — суммарное число узлов, m — длина второго списка».
2. **Время это или память.** Фраза без уточнения читается как «не понимаю».
3. **Средний / худший / амортизированный.** Для хеша и динамического массива это разные вещи.

---

## 2. Нотация: минимум

| Обозначение | Смысл | Как говорить |
|---|---|---|
| **O(f)** | верхняя граница, «не хуже чем» | «не превышает», «порядка» |
| **Θ(f)** | точная граница (сверху и снизу) | «ровно», «зависит линейно» |
| **Ω(f)** | нижняя граница, «не быстрее чем» | «не может быть быстрее» |

На интервью достаточно **O** — это стандарт де-факто. Но **O** — это верхняя граница, а границы вложены: O(1) ⊂ O(n) ⊂ O(n²). Алгоритм за O(1) формально работает и за O(n), поэтому одна буква «O» сама по себе ничего не говорит о качестве решения.

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

Три режима:

- **лучший / средний / худший** — по входным данным (worst case почти всегда то, что хотят услышать);
- **амортизированный** — «на одну операцию в среднем по длинной серии», даже если отдельная операция дорогая (push в динамический массив);
- **ожидаемый (expected)** — по случайности (хеш без коллизий: O(1) ожидаемое, O(n) худшее).

Полезные нижние границы, на которые можно ссылаться:

- просмотреть все n элементов **невозможно** быстрее Ω(n) — «O(log n), чтобы найти минимум в неотсортированном массиве» — ошибка;
- сортировка сравнениями — Ω(n log n), поэтому если задача сводится к сортировке, дешевле не выйдет без специальных условий (маленький диапазон значений → counting sort O(n)).

---

## 3. Как выводить время — 5 правил

**Правило 1. Последовательные блоки складываются, вложенные умножаются.**

```
for i in 1..n        # n
  for j in 1..n      #   x n
    x                # = O(n^2)
```

Операции в теле (сравнение, сложение, доступ к элементу массива) стоят O(1) — считаются они, а не строки кода. Скрытую работу встроенных методов надо считать тоже: `arr.sort` — это O(n log n) в одной строке, `arr.include?(x)` внутри цикла — O(n) на каждый вызов (см. §7).

**Правило 2. Константы и младшие члены выбрасываются — но только те, что действительно константы.**
O(2n + 5) = O(n), O(n² + n log n) = O(n²). Фиксированный алфавит — тоже константа: **O(26n) = O(n) по времени**, 26 от входа не зависит.

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

| Множитель | Константа? | Как писать |
|---|---|---|
| 26 (латинский алфавит), 128 (ASCII) | да, фиксирован | O(26n) = O(n) |
| k = размер окна (#14) | **нет, параметр входа** | O(n log k) |
| k = число списков (#20) | **нет, параметр входа** | O(N log k) |
| k = длина строки (#9) | **нет, зависит от данных** | O(n·k log k) |

Двухпараметрическую сложность проговаривают с обеими переменными: «O(n·k), где n — число элементов, k — размер окна; при k = n деградирует до O(n²)». Отсюда же требование всегда называть, что такое n и что такое k: «O(nk)» без определения k не сообщает слушателю, константа это или параметр.

**И отдельно про память — это другое утверждение.** Фиксированный алфавит даёт **O(1) дополнительной памяти** (счётчик на 26 ячеек не растёт со входом), при этом время остаётся O(n). «O(26n) = O(n) по времени» и «O(1) по памяти» — два независимых вывода, их можно (и нужно) назвать оба.

**Пограничный случай.** В Group Anagrams (#9) условие ограничивает длину строки k ≤ 100 — формально константа, значит асимптотически O(n). Но O(n·k log k) сохраняют, потому что оно описывает форму алгоритма (сортируем каждую строку). Если интервьюер ждёт O(n), а названо O(n·k log k) — это не ошибка, но стоит добавить: «k ограничена константой из условия».

Мнемоника: **константы выбрасываем, параметры входа — нет, и всегда говорим, что именно выбросили.**

**Правило 3. Вложенный цикл не всегда O(n²) — считать надо суммарное число итераций, а не вложенность.**
Классический O(n²) — это два независимых полных прохода. Но если внутренний цикл двигает тот же указатель, что и внешний, суммарно он проходит не больше n шагов:

```
while l < r                  # два указателя сходятся навстречу
  if need_move_l then l += 1
  else                 r -= 1
```

Так устроены два указателя (#1, #3), монотонная deque (#15) и разворот списка (#21): индекс, который сдвинулся, назад не возвращается, поэтому на весь алгоритм приходится O(n) шагов, хотя вложенность в коде есть. Это амортизация — см. §6.
Отдельно: два прохода по массиву — O(2n) = O(n), число проходов на сложность не влияет.

**Правило 4. Рекурсия — это рекуррентное соотношение.** Считать надо общее число вызовов, а не «глубину». Общий случай T(n) = aT(n/b) + O(n^d): если d больше log_b(a) — доминирует работа на уровне; равна — добавляется множитель log n; меньше — доминирует ветвление.

| Рекуррентность | Время | Стек рекурсии | Где встречается |
|---|---|---|---|
| T(n) = 2T(n/2) + O(n) | O(n log n) | O(log n) | mergesort, divide & conquer |
| T(n) = T(n/2) + O(1) | O(log n) | O(log n) | бинарный поиск |
| T(n) = T(n-1) + O(1) | O(n) | O(n) | рекурсивный обход списка |
| T(n) = 2T(n-1) + O(1) | O(2^n) | O(n) | перебор подмножеств |
| T(n) = T(n-1) + T(n-2) + O(1) | O(2^n), точнее O(1.618^n) | O(n) | Фибоначчи без мемоизации |

Обход дерева: O(n) по времени всегда; разница только в памяти — O(h), где h — высота (см. §4).

**Правило 5. Откуда берётся log.** Логарифм появляется там, где на каждом шаге область делится примерно пополам:

- бинарный поиск по массиву (#25);
- бинарный поиск по ответу («минимальная скорость, при которой успеем за h часов»);
- операции с кучей (push/pop) и balanced tree;
- mergesort: глубина log n при работе O(n) на уровень.

`log n` — почти константа: log₂(10^6) ≈ 20, log₂(10^9) ≈ 30, log₂(10^18) ≈ 60. Если видите log в ответе — это почти всегда «каждый шаг отбрасывает половину».

Осторожно с quicksort: в среднем O(n log n), но при неудачных опорных элементах глубина рекурсии растёт до n и время становится O(n²) — например, на уже отсортированном входе. Mergesort и heapsort дают O(n log n) в худшем случае.

---

## 4. Как выводить память

Главная привычка: **объявлять, о какой памяти речь**.

| Тип | Считается? | Пример |
|---|---|---|
| **Вход** | не считаем | массив nums |
| **Выход** | называть отдельно | список интервалов O(k) |
| **Дополнительная (auxiliary)** | считается | хеш-таблица, стек, deque |
| **Стек рекурсии** | **считается** | DFS по сетке до O(R·C); вырожденное дерево — до O(n) |

Частые ошибки:

- **«In-place» — только если O(1) дополнительной.** Два указателя — O(1); перезапись массива — O(1); сортировка стандартной библиотекой — O(log n) на стек, не O(1).
- **Рекурсия почти никогда не O(1) по памяти.** Reverse Linked List рекурсивно — O(n) дополнительной, итеративно — O(1). Классическая ловушка (задача #21).
- **Выход ≠ дополнительная память.** В Container With Most Water (#1) O(1): ответ — одно число, памяти под него не нужно. В Squares of a Sorted Array (#3) O(1) дополнительной, но сам результат — новый массив на n элементов.
- **Не забывать стек BFS/DFS.** Number of Islands (#22): время O(R·C), память O(R·C) в худшем (рекурсия по сетке из одной суши + очередь BFS). Для больших сеток это реальный риск.
- **Мемоизация превращает время в память.** Фибоначчи: наивно время O(2^n) и стек O(n); с мемоизацией время O(n), память O(n); итеративно двумя переменными — время O(n), память O(1). Ускорение всегда оплачивается памятью — либо её ростом, либо потерей общности.
- **Асимптотика ≠ байты.** O(n) памяти при n = 10^6 — это либо 1 МБ (`bytearray`), либо десятки мегабайт (список Python-объектов). Если спросят про реальную память, а не про асимптотику, отвечать надо в байтах.

---

## 5. Шпаргалка «паттерн → сложность»

| Паттерн | Время | Доп. память | Задачи |
|---|---|---|---|
| Два указателя | O(n) | O(1) | #1, #2, #3, #4 |
| Sliding window + счётчики | O(n) | O(1) (фиксированный алфавит) | #5, #6 |
| Sliding window + монотонная deque | O(n) | O(k) | #15 |
| Sliding window + две кучи | O(n log k) | O(k) | #14 |
| Префиксные суммы + хеш | O(n) | O(n) | #11 |
| Хеш-таблица в один проход | O(n) ожидаемое | O(n); O(1) при фиксированном алфавите | #7, #8, #10 |
| Ключ-канонизация (сортировка ключей) | O(n·k log k) | O(n·k) | #9 |
| Сортировка + линейный проход | O(n log n) | O(n) результат | #12; #24 — вариант «отсортировать уникальные» |
| Стек | O(n) | O(n) | #13 |
| XOR | O(n) | **O(1)** | #7 (ради этого и задача) |
| Greedy, один проход, два состояния | O(n) | O(1) | #17, #18, #19 |
| Куча / k-way merge | O(N log k) | O(k) | #20; #24 — вариант «куча из уникальных» |
| Разворот указателей | O(n) | O(1) итер. / O(n) рекурс. | #21 |
| Итератор с кэшем | O(1) на операцию | O(1) | #16 |
| BFS/DFS по графу или сетке | O(V+E) / O(R·C) | O(V) / O(R·C) | #22 |
| Обход дерева | O(n) | O(h): O(n) вырожденное, O(log n) сбалансированное | #26, #27, #29 |
| Обход дерева + сравнение поддеревьев | O(n·m) наивно / O(n+m) с хешами | O(h) / O(n+m) | #28 |
| Бинарный поиск | O(log n) | O(1) | #25 |
| Сложение строками | O(max(n,m)) | O(1) (+выход) | #30, #31 |
| Умножение строками (школьное) | O(n·m) | O(n+m) | #32 |
| Бэктрекинг / все варианты | O(2^n) или O(n·2^n) | O(n) стек; результат может быть экспоненциальным | #23 |

---

## 6. Амортизация

- **Динамический массив (Ruby Array#push / Python list.append)**: отдельная вставка иногда копирует весь массив (O(n)), но в серии каждая вставка O(1) амортизированно. Почему: при каждом расширении копируется 1 + 2 + 4 + ... + n < 2n элементов — то есть O(n) копирований на n вставок.
- **Хеш-таблица**: вставка/поиск O(1) ожидаемо, O(n) в худшем (все ключи в одну корзину). Расширение таблицы — амортизированно O(1), по той же причине: рехеширование удваивает таблицу.
- **Монотонная deque** (Sliding Window Maximum #15): каждый элемент кладётся и вынимается не более одного раза, поэтому весь проход O(n), а не O(n·k).
- **Куча**: push/pop O(log n), peek O(1), heapify массива — O(n), а не O(n log n).
- **Union-Find**: практически O(α(n)) ≈ O(1) с path compression и union by rank; α(n) < 5 для любого реального n.

Фраза для интервью: «Каждая операция может быть O(k), но в сумме по всем n операциям — O(n), потому что каждый элемент кладётся в deque один раз».

---

## 7. Стоимость встроенных операций (Ruby / Python)

Ruby:

- `Array#sort` — O(n log n), по памяти O(log n) стек;
- `Array#include?` / `index` / `find` — **O(n)**; внутри цикла это скрытая O(n²);
- `Hash#[]` — O(1) ожидаемое;
- `Array#shift` — в MRI амортизированно **O(1)**: внутри буфера есть запас в начале, сдвиг — это передвинуть указатель (замер: 1,6 млн shift ≈ 66 мс, линейно). Но это свойство реализации, а не языка: на «замороженном» массиве или в другой реализации операция может копировать — O(n);
- `Array#unshift` — в MRI тоже амортизированно O(1), по той же причине; `Array#pop` — O(1);
- `String#+` в цикле — каждая конкатенация O(n) → весь цикл O(n²); надо `<<` или массив + `join`;
- `String#[]` / `slice` — O(k) по длине куска.

Python:

- `list.pop(0)` — **O(n)**: очередь на списке квадратична (замер: 400 тыс. `pop(0)` ≈ 30 секунд) → `collections.deque`;
- `"".join(list)` вместо `+=` в цикле;
- slicing копирует — O(k);
- `x in list` — O(n), `x in dict` — O(1) ожидаемое;
- для больших сеток `bytearray` вместо `list[list[bool]]`, для чисел — `array('i')` вместо `list`: список из 10^6 Python int — это десятки мегабайт (объекты + указатели), bytearray/array — на порядок меньше;

В обоих языках `s = s + chunk` в цикле — O(n²) (каждая конкатенация копирует строку): в Ruby нужен `<<`, в Python — список + `join`.

На интервью это важно: интервьюер часто спрашивает «а здесь вы делаете `include?` внутри `each` — какая итоговая сложность?». Ответ: O(n²).

---

## 8. Constraints → ожидаемая сложность

| Ограничение | Что подразумевается | Задачи |
|---|---|---|
| n ≤ 10 | O(n!), перестановки | — |
| n ≤ 20 | O(2^n) бэктрекинг | #23 |
| n ≤ 500 | O(n²) или O(n³) | #32 (n·m) |
| n ≤ 10^4 | O(n²): 10^8 операций, для Ruby/Python на грани | — |
| n ≤ 10^5 | **O(n log n)** комфортно, O(n) — идеал | #12, #20, #24 |
| n ≤ 10^6 | O(n) или очень аккуратный O(n log n) | #1, #3, #11, #22 |
| n ≤ 10^9 | O(log n) или O(1) | #25 |

Практический ориентир: ~10^8 простых операций в секунду для C-подобного кода и примерно на порядок меньше для Ruby/Python. O(n²) при n = 10^5 — это 10^10 операций, не пройдёт никогда; при n = 10^4 (10^8) для Ruby уже на грани — секунды.

Обратный ход важнее прямого: **от constraints к замыслу алгоритма**. Если n = 10^5 и задача про подмассивы — интервьюер почти наверняка ждёт префиксные суммы или окно, а не двойной цикл.

Отдельно: сложность **по числу бит** для числовых задач. `Add Strings` (#31) — это O(n) *по длине строки*, а не O(1), и именно это проверяет интервьюер.

---

## 9. Граничные случаи — чек-лист из 9 пунктов

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

1. **Пусто и один элемент** (`[]`, `""`, `None`/`nil`, пустой список списков).
2. **Все элементы одинаковые / все разные.**
3. **Отрицательные числа и ноль** (префиксные суммы, XOR, Max Water).
4. **Дубликаты** — особенно когда нужен индекс, а не значение (Two Sum #8: `[3,3]`, target 6 — проверять **до** вставки в хеш, иначе один элемент используется дважды).
5. **Границы диапазона**: k = 0, k = n, k > n, окно длиннее массива.
6. **Решения нет** — ответ 0 / −1 / пустой список, а не исключение (Two Sum #8, Subarray Sum #11).
7. **Вход уже упорядочен или обратно упорядочен** — вырожденный случай для сортировок, двух указателей и бинарного поиска.
8. **Переполнение и точность**: `mid = (left+right)/2` → `left + (right-left)/2`; квадраты могут переполнить 32-битный int; медиана при чётном k — float или int?
9. **Особые формы**: сетка 1×1, вырожденное дерево в цепочку (стек рекурсии!), строка из одного типа скобок, ведущие нули в Multiply Strings.

Формулировать не «есть edge cases», а конкретно: «если k > n — возвращаю пустой массив; если p длиннее s — сразу пустой список; дубликаты проверяю до вставки в хеш».

---

## 10. Эталонная таблица по 32 задачам

| # | Задача | Время | Доп. память | Главный edge case |
|---|---|---|---|---|
| 1 | Container With Most Water | O(n) | O(1) | n = 2; равные высоты; нули |
| 2 | Partition Labels | O(n) | O(1) (26 букв) | все символы разные; все одинаковые; 1 символ |
| 3 | Squares of Sorted Array | O(n) | O(1) (+O(n) выход) | все отрицательные; только нули; переполнение квадрата |
| 4 | Summary Ranges | O(n) | O(1) (+выход) | пустой массив; непрерывный диапазон; разрывы |
| 5 | Find All Anagrams | O(n) | O(1) (26 счётчиков) | p длиннее s; пустой p; дубликаты |
| 6 | Permutation in String | O(n) | O(1) | s1 длиннее s2; s1 = s2 |
| 7 | Single Number | O(n) | **O(1)** (XOR) | один элемент; отрицательные |
| 8 | Two Sum | O(n) | O(n) | нет решения; `[3,3]` t=6 — проверка до вставки |
| 9 | Group Anagrams | O(n·k log k) | O(n·k) | пустые строки; одна строка; все идентичны |
| 10 | Valid Anagram | O(n) | O(1) (26-массив) | разные длины → сразу false; пустые |
| 11 | Subarray Sum Equals K | O(n) | O(n) | negatives; k = 0; seed `{0: 1}`; проверка до вставки |
| 12 | Merge Intervals | O(n log n) | O(n) | пустой; касающиеся `[1,4],[4,5]`; вложенные |
| 13 | Valid Parentheses | O(n) | O(n) стек | пустая строка → true; только закрывающая; смешанные типы |
| 14 | Sliding Window Median | O(n log k) | O(k) | k = 1; k = n; чётное k (float?); дубликаты |
| 15 | Sliding Window Maximum | O(n) (deque) | O(k) | k = 1; k = n; убывающий массив |
| 16 | Peeking Iterator | O(1) на операцию | O(1) (один кэш) | пустой итератор; peek дважды; peek → next |
| 17 | Best Time to Buy and Sell Stock | O(n) | O(1) | убывающий → 0; один день |
| 18 | Best Time ... II | O(n) | O(1) | плоский график; одни падения |
| 19 | Best Time ... with Fee | O(n) | O(1) (2 состояния) | fee больше любой выгоды; fee = 0 |
| 20 | Merge k Sorted Lists | O(N log k) | O(k) heap; pairwise — O(1) итер. / O(log k) рекурс. | пустой массив списков; пустые списки внутри; k = 1 |
| 21 | Reverse Linked List | O(n) | **O(1)** итер. / O(n) рекурс. | пустой; один узел |
| 22 | Number of Islands | O(R·C) | O(R·C) худший | всё вода; всё суша (глубина рекурсии); 1×1; диагональ не считается |
| 23 | Remove Invalid Parentheses | O(n·2^n) | O(n) стек; ответ может быть экспоненциальным | строка уже валидна; пустая; несколько ответов → дедуп |
| 24 | Top K Frequent Words | O(n log k) | O(n) | k ≥ числа уникальных; тай-брейк лексикографией (O(k log k)); регистр |
| 25 | Binary Search | O(log n) | O(1) | пустой; границы; `left + (r-l)/2` от переполнения |
| 26 | Same Tree | O(n) | O(h) — O(n) в цепочке | оба nil; один nil; разная структура |
| 27 | Symmetric Tree | O(n) | O(h) | один узел; только левый ребёнок; равные значения не зеркальны |
| 28 | Subtree of Another Tree | O(n·m) наивно / O(n+m) с хешами | O(h) / O(n+m) | subRoot больше root; дубликаты значений; subRoot = root |
| 29 | Find Duplicate Subtrees | O(n) ожидаемое (ID-хеш) | O(n) | одинаковая форма с разными значениями; строковая сериализация даёт O(n²) на цепочке |
| 30 | Add Binary | O(max(n,m)) | O(1) (+выход) | `"0"+"0"`; перенос `"1"+"1"`; разная длина |
| 31 | Add Strings | O(max(n,m)) | O(1) (+выход) | перенос в конце; `"0"`; разная длина |
| 32 | Multiply Strings | O(n·m) | O(n+m) | `"0"` × `"123"`; ведущие нули; не переводить в int |

Закономерность: у 14 из 32 задач (#1–#7, #10, #17–#19, #21, #30, #31) ответ — линейное время и O(1) дополнительной памяти. И именно эти два числа дают половину балла в рубрике.

---

## 11. Скрипт ответа (довести до автоматизма)

Как только названа идея, сразу три предложения:

> **Время.** «Доминирует сортировка: O(n log n), остальное линейно.»
> **Память.** «Дополнительная O(n) — хеш-таблица; результат O(k) отдельно; вход не меняю.»
> **Границы.** «Пустой вход, k больше размера массива, дубликаты — проверяю до вставки в хеш.»

Плюс, если есть чем усилить:

- **амортизированный** аргумент (deque — каждый элемент обрабатывается один раз);
- **почему нельзя лучше** («быстрее O(n log n) не выйдет, потому что задача сводится к сортировке сравнениями»).

Это то, что отличает 3 от 2.

---

## 12. Что тренировать под текущий пробел

Системный разрыв один: сложность и edge cases не проговариваются. Механика, которая закрывает его быстро:

1. Перед каждым билетом **вслух** произносить три блока из §11, даже если задача элементарная (Binary Search #25) — цель не решить, а довести называние n, времени и памяти до рефлекса.
2. В билете заполнять три разборные строки: **Время / Память / Граничные случаи** — они уже добавлены в `_ticket-template.md`, осталось их не пропускать.
3. Отработать 4 задачи, где сложность реально неочевидна: #11 (префиксы), #14 (две кучи), #20 (heap vs попарное слияние — обе версии O(N log k), но память разная), #15 (почему deque даёт O(n) вместо O(n log k) с кучей).
4. На Hard-задачах (#14, #23, #28, #29) заранее заучить формулировки «экспоненциально» / «ожидаемое O(n)» / «O(n·m) наивно, O(n+m) с хешами»: единственный риск там — назвать неверную сложность и потерять балл.