• ✨ Оглавление
  • 🧠 Что такое алгоритмическая сложность (на пальцах)
  • 📐 Формальные нотации (коротко и формально)
  • ✍️ Как оценивать сложность — пошаговая методика
  • 🔢 Правила упрощения (эмпирические)
  • 🔁 Виды оценок времени (когда что говорить)
  • 🧾 Примеры обычного анализа (с шагами)
  • 🧩 Master Theorem — кратко (очень полезно для рекурсий)
  • ⚡ Amortized анализ — методы
  • 🧨 Каверзные моменты / ловушки (что часто спрашивают)
  • 📚 Таблица: типичные сложности (быстрый справочник)
  • 🧭 Сложности популярных операций и структур (часто спрашивают)
  • 🧾 Как решать рекурренту — три способа
  • 🧪 Практические измерения и когда асимптика обманчива
  • 🧨 Каверзные (интервьюерские) вопросы + краткие ответы
  • ✅ Короткая шпаргалка (что говорить на собесe — 1–2 минуты)
  • 🧰 Полезные приёмы для интервью (чеклист)

⬆ Вернуться к главной

Алгоритмическая (асимптотическая) сложность — это способ описать как растёт потребление ресурсов (время, память, I/O и т.д.) алгоритмом при росте размера входа n. Мы обычно интересуемся поведением при больших n — какие термы доминируют и как быстро растёт функция затрат.

Основное назначение:

• Сравнить алгоритмы независимо от конкретного железа/компилятора.
• Понять, будет ли алгоритм масштабироваться при больших данных.

• Big O — O(f(n)): верхняя граница (asymptotic upper bound). Формально: f(n) = O(g(n)) если ∃C>0, n0: ∀n>n0: f(n) ≤ C·g(n).

• Big Ω — Ω(f(n)): нижняя граница (asymptotic lower bound). Формально: f(n) = Ω(g(n)) если ∃C>0, n0: ∀n>n0: f(n) ≥ C·g(n).

• Big Θ — Θ(f(n)): точная асимптотика (и верхняя, и нижняя). f(n) = Θ(g(n)) если f = O(g) и f = Ω(g).

• little-o — o(f(n)): строго меньше асимптотически (f(n) / g(n) → 0).

• Анализ времени vs. анализа памяти: T(n) — время; S(n) — память.

1. Определите меру входа n Что считать размером? Количество элементов в массиве, число вершин в графе, длина строки и т.д.

2. Выберите метрику Время (операций) — чаще всего. Можно считать элементарные операции (сравнение, присваивание, арифметика).

3. Считайте базовые операции Прикиньте, сколько раз выполняется «дорогая» операция в зависимости от n.

4. Определите лучшие/средние/худшие случаи

   • best-case (минимум), average-case (ожидаемая по распределению), worst-case (максимум) — обычно мы оцениваем worst-case.
   • amortized — средняя стоимость операции в последовательности операций (важно для структур типа динамического массива, union-find).

5. Упростите функцию Уберите константы и низкоуровневые члены: 3n^2 + 10n + 100 -> Θ(n^2).

6. Если рекурсия — выведите рекурренту Решите её (подходы: подстановка, дерево рекурсии, Master theorem, characteristic equation).

7. Проверьте крайние случаи и скрытые стоимости Например, вычисление GetHashCode() для строк — O(k) где k длина строки; сравнение строк O(k) в худшем случае и т.д.

• Убираем множители: 2·n → O(n).
• Убираем константы: O(1) = O(1000).
• Доминирует старший терм: n^2 + n → O(n^2).
• Для сумм/последовательных блоков — берём максимум: O(f(n)) + O(g(n)) = O(max(f,g)).
• Для вложенных циклов — перемножаем: for i..n for j..n -> O(n^2).
• Для последовательных независимых циклов — сумма: for i..n и for j..m → O(n+m).

• Worst-case — что обычно требуется на собесе.
• Average-case — если данные случайны и вы можете аргументировать распределение.
• Best-case — редко спрашивают, но полезно для contrast.
• Amortized — для операций, где периодически бывают дорогие шаги, но средне — дешево.

Пример 1 — двойной вложенный цикл

for (int i = 0; i < n; i++)
  for (int j = 0; j < n; j++)
    O(1);

Анализ: i от 0 до n-1 (n итераций), j — n итераций → всего n·n = n² операций → O(n^2).

Пример 2 — геометрический шаг

for (int i = 1; i < n; i *= 2)
  O(1);

i принимает значения 1,2,4,8,... до n → количество итераций ≈ log2 n → O(log n).

Пример 3 — consecutive loops

for i in 1..n { O(1) }
for j in 1..n { O(1) }

Анализ: O(n) + O(n) = O(2n) → O(n).

Для рекурренты вида T(n) = a T(n/b) + f(n) (a ≥1, b>1):

• Пусть d = log_b(a).

1. Если f(n) = O(n^{d - ε}) для некоторого ε>0 → T(n) = Θ(n^d) (делитель доминирует).
2. Если f(n) = Θ(n^d * log^k n) → T(n) = Θ(n^d * log^{k+1} n) (равновесие).
3. Если f(n) = Ω(n^{d + ε}) и a f(n/b) ≤ c f(n) для некоторого c<1 (regularity) → T(n) = Θ(f(n)) (функция сверху доминирует).

Примеры

• MergeSort: T(n)=2T(n/2)+Θ(n) → d=1 → T=Θ(n log n).
• Binary search: T(n)=T(n/2)+Θ(1) → d=0 → T=Θ(log n).

• Aggregate method: суммарная стоимость m операций / m.
• Accounting method: присваиваем кредит/дебет операциям (charge more on cheap ops to «накопить» на дорогие).
• Potential method: вводим потенциал состояния, показывающий накопленный заряд.

Пример: динамический массив (capacity doubling) — append amortized O(1), но отдельное расширение O(n).

1. Amortized vs average vs worst — List<T>.Add() amortized O(1), но индивидуальное расширение O(n). Hash table Insert — amortized O(1), worst O(n) при ресайзе или атаке коллизиями.

2. Операция «O(1)» — не всегда быстрая — O(1) может быть дорогостоящей константой (например, системный вызов).

3. Сравнения строк/хэшей — Dictionary<string, ...>: вставка/поиск аморт. O(1), но GetHashCode и сравнение строк — O(k) (длина строки). Хеширование не «волшебно O(1)» для длинных ключей.

4. Преобразования generic/boxing — List<object> и хранение int приведёт к boxing и O(1) становится дороже (аллоцирует). List<int> — никаких бокcингов.

5. Массивы ковариантны, generic классы нет — string[] можно присвоить object[] — опасно и может вызвать ArrayTypeMismatchException. List<string> нельзя присвоить List<object>.

6. Смешивание сложностей — два подряд вложенных цикла for i..n for j..i → O(n^2) (сумма 1..n ~ n(n+1)/2).

7. Рекурсия Фибоначчи — Наивная рекурсия fib(n) → экспоненциальная O(φ^n). С мемоизацией → O(n).

8. Big O vs practical performance — Алгоритм O(n) с большой константой может быть хуже, чем O(n log n) для малых n. Всегда учитывать константы и кэш.

9. LOH, копирование больших данных — Большие объекты (строки >85kB, большие массивы) попадают в LOH и влияют на сборку мусора.

10. Вложенные структуры данных — Операции на структурах внутри структуры добавляют сложность. Пример: удаление по значению в List<List<T>> — нужно учитывать как поиск в внешнем списке, так и в внутреннем.

• O(1) — доступ по индексу в массиве, чтение поля.
• O(log n) — бинарный поиск, поиск в сбалансированном BST.
• O(n) — линейный проход, поиск в несортированном массиве.
• O(n log n) — сортировки сравнения типа merge/heap/avg quicksort.
• O(n^2) — простые сортировки (bubble/insert/selection), двойные вложенные циклы.
• O(2^n) — перебор подмножеств, наивный TSP/фибрекурсия.
• O(n!) — полные перестановки (brute-force TSP).

• Array access arr[i] — O(1).
• Insert at end (dynamic array) — amortized O(1), worst O(n) на ресайзе.
• Insert at beginning of array — O(n).
• LinkedList insert (given node) — O(1); search — O(n).
• Dictionary/HashMap lookup/insert/delete — амортиз. O(1), worst O(n).
• Sorted array insert — O(n) (сдвиг).
• Balanced BST (AVL, Red-Black) ops — O(log n) worst.
• Heap push/pop — O(log n).
• BFS/DFS — O(V + E).
• Dijkstra with binary heap — O(E log V); с Fibonacci heap — O(E + V log V).
• Floyd-Warshall — O(n^3).
• Bellman-Ford — O(VE).
• KMP string match — O(n + m).
• Regex — может быть экспоненциальным при backtracking (в зависимости от engine/pattern)!

1. Подстановка/индукция — прикинуть формулу и доказать.
2. Дерево рекурсии — разбить на уровни и суммировать взносы.
3. Master theorem — для aT(n/b) + f(n) (см. выше).

Пример: T(n) = 3T(n/4) + n → d = log_4 3 ≈ 0.792. f(n)=n = n^{1} -> f grows faster -> third case -> T(n)=Θ(n).

• Профилирование — для узких мест (hotspots) используйте профайлеры, а не догадки.
• Память/кэш — алгоритм с хорошей кэш-локальностью может опередить «лучший» по O-нотации.
• Вводные данные — распределение входа (почти отсортированные массивы) меняет поведение quicksort.
• Параллелизм — при параллелизации важно смотреть на work (общее число операций) и span (критический путь). Ограничивает Amdahl’s law.

1. «Что такое O(1)?» — Время не зависит от n (константное), но константа может быть большой.

2. «Как отличить O(n) от O(n log n) на практике?» — Для больших n O(n log n) растёт быстрее; смоделируйте/профилируйте; для небольших n константы важнее.

3. «Почему HashMap — O(1), но иногда O(n)?» — Амортизированно O(1), но в худшем случае из-за плохих хешей/коллизий/атаки может деградировать до O(n).

4. «Можно ли ускорить сортировку ниже n log n?» — Для сортировки на сравнениях — нет (lower bound Ω(n log n)). Для специальных случаев (целые в диапазоне k) — counting/radix sort дают O(n + k).

5. «Сколько времени займёт вызов Equals для строки?» — В худшем — O(k) (длина строки), но часто быстрое сравнение ссылок при интернированных литералах.

6. «Почему у quicksort средний O(n log n), а worst O(n^2)?» — При плохом выборе опорного элемента (pivot) разделение может быть крайне несбалансированным. Рандомизация/выбор медианы помогает.

7. «Что такое amortized O(1)?» — Средняя стоимость операции в последовательности операций; индивидуальные операции могут быть дорогими.

8. «Дайте пример алгоритма с экспоненциальной сложностью, который можно сделать полиномиальным» — Наивный Fibonacci O(φ^n) → с мемоизацией/DP O(n).

9. «Почему массивы быстрее LinkedList в реальности, хотя асимптотика вставки O(1) у LinkedList?» — Кэш-локальность: массивы компактны в памяти, меньше промахов кэша → быстрее на практике.

10. «Что такое lower bound Ω(n log n) для сравнения сортировок?» — Любая сортировка, основанная на сравнениях, требует по крайней мере порядка n log n сравнений в худшем/среднем случае (информационная нижняя граница).

• Алгоритмическая сложность описывает, как растут ресурсоёмкости алгоритма при увеличении входа n.
• Основные нотации: O (верхняя), Θ (точная), Ω (нижняя).
• Мы обычно оцениваем worst-case для надёжности; иногда average или amortized (для DS).
• Анализ: считать операции, упростить выражение (убрать константы и низшие члены).
• Важные техники: рекуррентные уравнения (Master theorem), амортизационный анализ, подсчёт вложенных циклов.
• Практика: профилировать, учитывать кэш, константы и распределение входа.

• Всегда уточняй, что считается n.
• Скажи, worst/average/amortized — что ты считаешь.
• Если рекурсия — запиши рекурренту явно.
• Объясни константы и влияние кэша/памяти, если интервьюер смотрит глубже.
• При анализе сложных структур — укажи скрытые стоимости (аллоц, hash, copy).

⬆ Вернуться к главной

✨Dvurechensky✨