---
title: "Таблица сложности алгоритмов: что успеет пройти"
url: https://algopath.pro/ru/blog/tablitsa-slozhnosti-algoritmov
language: ru
summary: "Строка с размером входа обычно и решает, какой алгоритм тебе разрешён. Таблица, которая учится за пять минут, и что делать, когда ограничений не дали."
updated: 2026-10-15
---

# Таблица сложности алгоритмов: что успеет пройти

**Короткий ответ.** Сначала прочитай размер входа: он говорит, какая сложность разрешена. Компьютер делает около 100 миллионов простых операций в секунду. Поэтому при n до 20 можно перебрать все подмножества, до 5000 проходит n², до 100 000 нужен n log n, а около миллиарда нужен логарифм или формула.

 

Всё, что ниже, следует из этого числа и из того, что такое [временная сложность](https://ru.wikipedia.org/wiki/%D0%92%D1%80%D0%B5%D0%BC%D0%B5%D0%BD%D0%BD%D0%B0%D1%8F_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D1%8C_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%B0).

 

## Таблица

 

- **n до 10**: можно всё. Перебрать все перестановки это 3,6 миллиона.
- **n до 20**: все подмножества это миллион. Битовые маски живут здесь и почти нигде больше.
- **n до 500**: куб проходит. [Флойд](https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A4%D0%BB%D0%BE%D0%B9%D0%B4%D0%B0_%E2%80%94_%D0%A3%D0%BE%D1%80%D1%88%D0%B5%D0%BB%D0%BB%D0%B0), интервальная динамика.
- **n до 5000**: квадрат проходит. Все пары, почти вся динамика на строках.
- **n до 100000**: нужно n log n. Сортировка, куча, бинарный поиск внутри цикла, сбалансированные деревья.
- **n до 10 миллионов**: один проход, и дешёвый. Окна, префиксные суммы, счётчики.
- **n около миллиарда**: до каждого элемента дотронуться нельзя. Жди логарифм, формулу или [бинарный поиск](https://ru.wikipedia.org/wiki/%D0%94%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D1%8B%D0%B9_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA) по ответу.

 

Пять минут на заучивание. Убирает большинство неверных поворотов заранее.

 

У последней строки есть своя страница: [бинарный поиск по ответу](/ru/patterns/binary-search-on-answer).

 

## Читай в обратную сторону

 

Иди от границы к форме кода.

 

n log n обычно означает одну сортировку. Или один цикл с бинарным поиском внутри.

 

Значит идея с двумя вложенными проходами по 100 тысячам мертва до написания. Проверить уже написанную функцию можно в [калькуляторе Big O](/ru/big-o-calculator).

 

Вперёд, ты напишешь квадрат и узнаешь об этом при отправке.

 

Назад, эти полчаса не случаются.

 

## Другие числа

 

Внимание достаётся размеру входа. Ещё три строки несут столько же.

 

**Диапазон значений.** «Значения до 10⁶» это массив такого размера и прямой подсчёт.

 

«До 10⁹» означает, что нельзя. Нужен словарь или сжатие координат.

 

**Алфавит.** «Строчные латинские буквы» это 26 ячеек. Фиксированный массив заменяет словарь, константа падает.

 

Память становится O(1). Это приятно сказать вслух.

 

**Лимит памяти.** 256 МБ это примерно 64 миллиона четырёхбайтных чисел.

 

Таблица 100 тысяч на 100 тысяч не поместится. Какой бы красивой ни была рекуррента.

 

## На собеседовании этого обычно не дают

 

В олимпиадных задачах границы написаны. Интервьюеры их чаще всего не называют.

 

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

 

«Насколько большим бывает массив?» «Значения могут быть отрицательными?» По четыре секунды.

 

Оба меняют ответ. И показывают ровно тот рефлекс, который оценивают.

 

Проговори допущение и продолжай, даже если интервьюер сказал, что неважно.

 

Решение верно при озвученном допущении. Это сильнее, чем тихо ошибаться.

 

Эта идея входит в число пяти идей статьи [почему задачи сложные](/ru/blog/kak-nauchitsya-reshat-algoritmicheskie-zadachi).

 

## Когда граница выглядит странно

 

Странное ограничение это подсказка. Её оставили тебе.

 

n до 20 при огромном диапазоне значений это задача на битовую маску. Она объявляет себя сама.

 

Маленькое n рядом с кучей запросов значит: посчитай один раз, отвечай быстро.

 

Ровно 10⁵ рядом с лимитом в секунду значит n log n. Ничего медленнее.

 

Эти числа выбраны намеренно. Прочитать их бесплатно.

 

## Где это тренируется

 

В [AlgoPath](/ru) чтение ограничений стоит на шаге 09 [«Big-O: имя для того, как быстро растёт работа»](/ru/steps/big-o-and-constraints), до первого паттерна.

 

Дальше каждая задача в тренажёре приходит с границами. Именно поэтому.

 

Первые 33 шага бесплатные.

 

Нотация сложности разобрана в статье [Big O без математики](/ru/blog/big-o-prostymi-slovami).