Как сдать анализ сложности алгоритмов на ЕГЭ по информатике: шорткаты и советы

В заданиях на анализ сложности алгоритмов (например, номер 6 или 12) дают псевдокод или описание алгоритма. Нужно:
- Определить, сколько раз выполняется тело цикла (сложность по времени).
- Оценить затраты памяти (сложность по памяти).
- Сравнить два алгоритма — какой быстрее при больших n.

Типичные варианты: O(n) — линейный проход, O(n²) — вложенные циклы, O(log n) — деление пополам (бинарный поиск). На ЕГЭ чаще всего встречаются O(n) и O(n²), реже O(log n).

Важно: не нужно считать точное число операций — достаточно оценить порядок роста. Если количество операций растёт как n² — пиши O(n²).

1. **Считай вложенность циклов** — если циклы вложены, сложность перемножается. Один цикл — O(n), два вложенных — O(n²), три — O(n³).

2. **Игнорируй константы** — O(2n) = O(n), O(100n²) = O(n²). На ЕГЭ константы не важны.

3. **Логарифм — это деление пополам** — если на каждом шаге массив уменьшается вдвое (бинарный поиск, рекурсия с делением), сложность O(log n). Если видишь while с делением на 2 — сразу O(log n).

Самая частая ошибка — путать O(n) и O(n²), когда циклы не вложенные, а последовательные. Например:
for i=1 to n: a[i]=0
for j=1 to n: b[j]=0
Это два последовательных цикла — сложность O(n)+O(n)=O(n), а не O(n²).

Вторая ошибка — забывать про сложность по памяти. Если создаётся массив размера n, то память O(n). Если массив размера n×n — O(n²).

Третья — неправильно оценивать рекурсию. Например, рекурсивный Фибоначчи без мемоизации имеет сложность O(2ⁿ), а не O(n). На ЕГЭ рекурсия редко бывает, но если есть — смотри, сколько раз вызывается функция.

Задача: Алгоритм вычисляет значение F(n), где n — натуральное число, по следующему правилу:
F(0)=1; F(n)=F(n-1)+F(n-2) для n>0.
Определите временную сложность алгоритма (в терминах O-большое).

Решение: Это рекурсивный алгоритм без запоминания. Каждый вызов порождает два новых вызова, глубина рекурсии n. Количество вызовов — около 2ⁿ, поэтому сложность O(2ⁿ).

Если бы использовалась мемоизация (запоминание уже вычисленных значений), сложность стала бы O(n). На ЕГЭ часто дают именно рекурсию с экспоненциальным ростом — будь внимателен.

На платформе nastavnik-ai.ru ты можешь выбрать персонажа, который объяснит тему именно так, как тебе понятно. Хочешь — Витёк разложит "по-братски": "Слышь, сложность — это сколько раз комп тупит. Если цикл в цикле — квадрат, понял?" Хочешь — Анна Сергеевна по-советски: "Товарищ, запомните: O(n) — это линейная зависимость, как шаги на параде". А если хочешь мотивации — Криштиану Роналду скажет: "Тренируйся как Месси на тренировке — каждый день решай задачи, и сложность станет простой".

Ты говоришь голосом задачу — персонаж отвечает голосом. Можно даже сфоткать условие — камера распознает и разберёт. Весь процесс — как диалог с репетитором, только дешевле и веселее.

Репетитор по информатике берёт от 2000₽ за час. А тут — 995₽ за целый месяц доступа ко всем 12 предметам (математика, русский, физика, информатика и т.д.). Это как одна пицца, только вместо калорий — знания. И скидка 50% на старте фиксируется навсегда. Можно вообще начать бесплатно — три пробных урока без карты.