Анализ сложности алгоритмов: подготовка к ЕГЭ по информатике
Анализ сложности алгоритмов — одна из ключевых тем в курсе информатики 10-11 классов и обязательный элемент ЕГЭ. Она позволяет оценить, насколько эффективно программа использует время и память при увеличении входных данных. Понимание асимптотической сложности (О-большое) помогает выбирать оптимальные алгоритмы и избегать неэффективных решений.
На экзамене эта тема встречается в заданиях на анализ программ, сравнение алгоритмов и оптимизацию. Часто ученики путают линейную сложность O(n) с квадратичной O(n²) или неверно оценивают сложность рекурсивных функций. В этом разборе мы систематизируем знания, разберём типовые задачи и дадим алгоритм действий для правильного определения сложности.
Для успешной сдачи ЕГЭ важно не просто запомнить определения, но и научиться применять их на практике. Мы пройдём от базовых понятий до сложных примеров, включая анализ рекурсии и сравнение алгоритмов. Материал будет полезен как для самостоятельной подготовки, так и для занятий с репетитором.
Без карты, без кредитки. Выбери персонажа — учи голосом, побеждай в баттлах.
Что такое сложность алгоритма: время и память
Сложность алгоритма — это характеристика, показывающая, как быстро растёт количество операций (временная сложность) или объём используемой памяти (пространственная сложность) при увеличении размера входных данных n. Обычно используют О-большое: O(f(n)), где f(n) — функция роста.
Наиболее распространённые виды сложности:
- O(1) — константная: время не зависит от n.
- O(log n) — логарифмическая: время растёт медленно (например, бинарный поиск).
- O(n) — линейная: время пропорционально n.
- O(n log n) — логарифмическая линейная (эффективные сортировки).
- O(n²) — квадратичная: время растёт как квадрат n (вложенные циклы).
- O(2ⁿ) — экспоненциальная: очень быстро (например, рекурсивный перебор).
Важно различать временную и пространственную сложность. Алгоритм может быть быстрым, но требовать много памяти, или наоборот. В задачах ЕГЭ чаще спрашивают временную сложность, но пространственная тоже встречается, особенно при оценке рекурсивных алгоритмов.
Дан фрагмент программы:
for i in range(n):
a[i] = 0
Определите временную сложность алгоритма.
Цикл выполняется n раз, внутри одна операция присваивания. Количество операций пропорционально n. Сложность O(n).
Дан фрагмент:
for i in range(n):
for j in range(n):
a[i][j] = i+j
Определите временную сложность.
Внешний цикл выполняется n раз, внутренний — n раз для каждого i. Итого n*n = n² операций. Сложность O(n²).
Как определять сложность O(n), O(n²), O(log n)
Чтобы определить сложность, нужно проанализировать количество операций в зависимости от n. Основные правила:
- Один цикл от 1 до n — O(n).
- Вложенные циклы, каждый до n — O(n²).
- Если цикл с шагом умножения (например, i = i*2) — O(log n).
- Рекурсивные вызовы: если каждый вызов порождает один подвызов с уменьшением n в 2 раза — O(log n); если два подвызова — O(2ⁿ) (но на ЕГЭ обычно O(n) или O(log n)).
Рассмотрим примеры из ЕГЭ: часто дают фрагмент кода, где нужно выбрать правильную оценку сложности. Важно не путать O(n) и O(n²): если внутри цикла есть ещё один цикл, но его количество итераций не зависит от n (например, константа 10), то сложность остаётся O(n).
Дан алгоритм:
while n > 0:
n = n // 2
Определите сложность.
На каждой итерации n уменьшается вдвое. Количество итераций равно log₂(n). Сложность O(log n).
Дан фрагмент:
for i in range(n):
for j in range(10):
print(i+j)
Определите сложность.
Внешний цикл — n итераций, внутренний — 10 (константа). Общее количество операций 10n ≈ O(n).
Сравнение алгоритмов по сложности
При сравнении алгоритмов смотрят на асимптотическую сложность при больших n. Например, O(log n) быстрее O(n), O(n) быстрее O(n log n), O(n log n) быстрее O(n²). На практике для малых n константа может играть роль, но на ЕГЭ сравнивают именно по O-большому.
Типовые задания: даны два алгоритма с разными сложностями, нужно определить, какой эффективнее для заданного n. Или даны времена выполнения для одного n, нужно предсказать для другого.
Важно уметь оценивать сложность рекурсивных функций: если функция вызывает себя один раз с уменьшением аргумента на константу — O(n); если с делением на 2 — O(log n); если два вызова — O(2ⁿ) (но в ЕГЭ обычно O(n) для рекурсии с одним вызовом).
Алгоритм A имеет сложность O(n²), алгоритм B — O(n log n). При n=1000 алгоритм A выполняется за 1 секунду. За какое время выполнится алгоритм B при тех же условиях?
Для A: время пропорционально n², для B — n log n. При n=1000: n²=1e6, n log n ≈ 1000*10=10000. Отношение 1e6/10000=100. Значит, B выполнится в 100 раз быстрее: 1/100 = 0.01 секунды.
Дана рекурсивная функция:
def f(n):
if n <= 1:
return 1
return f(n-1) + f(n-1)
Определите временную сложность.
Каждый вызов порождает два подвызова, глубина рекурсии n. Количество вызовов 2ⁿ. Сложность O(2ⁿ). (Внимание: в ЕГЭ редко дают такую, чаще с одним вызовом.)
Практические советы для решения задач ЕГЭ
При решении задач на сложность алгоритмов на ЕГЭ следуйте алгоритму:
1. Определите, сколько раз выполняется каждая операция.
2. Если есть циклы, оцените количество итераций каждого.
3. Для рекурсии — количество вызовов.
4. Выберите доминирующий член (самый быстрорастущий).
5. Запишите ответ в виде O(...).
Частые ошибки:
- Путают O(n) и O(n²) при наличии вложенных циклов, где внутренний зависит от внешнего.
- Не учитывают, что константные множители отбрасываются (O(2n) = O(n)).
- Считают сложность O(log n) для циклов с шагом +2 (это O(n)).
- Неправильно оценивают сложность рекурсии: если один вызов с n-1 — O(n); если два вызова — O(2ⁿ).
Рекомендуется потренироваться на реальных заданиях из сборников ФИПИ и демоверсий. Также полезно использовать визуализацию алгоритмов для понимания роста сложности.
Часто задаваемые вопросы (FAQ)
Частые вопросы
Без карты, без кредитки. Выбери персонажа — учи голосом, побеждай в баттлах.