Вычислительная сложность алгоритмов. Оценка O(f(n)): ЕГЭ по информатике

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

Что нужно знать

• O(f(n)) — множество функций, растущих не быстрее f(n) с точностью до константы: g(n)=O(f(n)), если существуют C>0 и n0 такие, что для всех n≥n0 выполняется 0≤g(n)≤C·f(n).
• Константные множители и слагаемые низшего порядка не влияют на O: O(3n^2+5n+7)=O(n^2).
• Основные классы сложности по возрастанию: O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(n^3) < O(2^n) < O(n!).
• Вложенные циклы: если внешний выполняется n раз, внутренний — m раз, сложность O(n·m); при одинаковом числе итераций — O(n^2).
• Одиночный цикл по n элементам — O(n); цикл с шагом, уменьшающим счётчик в 2 раза, — O(log n).
• Рекурсивные алгоритмы: сложность оценивается через рекуррентные соотношения (например, T(n)=2T(n/2)+O(n) даёт O(n log n)).

Термины и понятия

• Асимптотическая сложность: оценка роста времени работы или памяти алгоритма при стремлении размера входа к бесконечности.
• O(f(n)): класс функций, растущих не быстрее f(n) с точностью до постоянного множителя; верхняя асимптотическая оценка.
• Размер входа n: параметр, характеризующий объём входных данных (число элементов массива, длина строки, значение числа и т.п.).
• Константная сложность O(1): время работы не зависит от размера входа.
• Логарифмическая сложность O(log n): типична для алгоритмов, делящих задачу пополам на каждом шаге (бинарный поиск).
• Линейная сложность O(n): один проход по входным данным.
• Квадратичная сложность O(n^2): обычно два вложенных цикла по n.
• Экспоненциальная сложность O(2^n): часто у алгоритмов полного перебора подмножеств.

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

• Путают O(f(n)) с точным числом операций: O(n) не означает ровно n операций, а лишь порядок роста.
• Оставляют в записи O константные множители и младшие слагаемые: пишут O(2n) или O(n^2+n) вместо O(n) и O(n^2).
• Неверно оценивают вложенные циклы: считают O(n) вместо O(n^2), если оба цикла зависят от n.
• Забывают, что цикл с делением/умножением счётчика даёт O(log n), а не O(n).

Как пройти тему

В курсе «Информатика» тема «Вычислительная сложность алгоритмов. Оценка O(f(n))» занимает 1 занятие по 40 минут: репетитор объясняет материал, задаёт вопросы как на экзамене, разбирает ваши ответы и в конце ставит оценку. Это обзор темы, полный разбор — в занятии. ИИ может ошибаться: проверяйте важное по учебнику. Занятия не заменяют живого репетитора и не гарантируют результат на экзамене.

Другие темы раздела

• Понятие алгоритма. Свойства алгоритмов. Способы записи
• Базовые алгоритмические конструкции: следование, ветвление, цикл
• Вспомогательные алгоритмы. Рекурсия
• Анализ алгоритмов. Определение результата работы алгоритма
• Поиск ошибок в алгоритмах. Отладка
• Обработка одномерных массивов: поиск, сортировка, статистика

← Предыдущая тема: Алгоритмы сортировки и их сложность
Следующая тема: Принципы построения компьютерных сетей. Топологии

Все темы: ЕГЭ по информатике