Анализ сложности алгоритмов

Что такое сложность алгоритма

Большая задача может решитьcя быстро, а маленькая внезапно «зависнуть» на длинном переборе. Анализ сложности помогает заранее понять, сколько времени и памяти потребует алгоритм, и выбрать решение, которое не подведёт на контрольной или экзамене. Ты научишься сравнивать алгоритмы не по скорости конкретного компьютера, а по тому, как меняется число действий при росте объёма данных.

Обычно размер входных данных обозначают буквой n. Это может быть количество чисел в массиве, символов в строке или вершин графа. Нас интересует не точное число операций, а порядок роста. Поэтому постоянные множители и менее значимые слагаемые часто не учитывают.

Так появляется асимптотическая оценка сложности, которую записывают как O(…). Читается она «о большое». Например, O(n) означает линейный рост: если данных стало в два раза больше, действий примерно тоже станет в два раза больше.

Основные классы сложности

Самые распространённые классы удобно запомнить от более эффективных к менее эффективным. O(1) — постоянная сложность: действие не зависит от размера входа. Получить элемент массива по известному индексу обычно можно за O(1).

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

Сложность	Идея	Пример
O(1)	одно действие	доступ по индексу
O(log n)	деление задачи	двоичный поиск
O(n)	один проход	поиск максимума
O(n²)	два вложенных прохода	сравнение всех пар

O(n²) часто появляется в двух вложенных циклах. При увеличении n в десять раз число действий может вырасти примерно в сто раз. Поэтому для больших массивов квадратичный алгоритм иногда становится неприемлемым.

Как считать сложность по шагам

Сначала определи, что именно считается размером входа. Затем найди главный повторяющийся блок: цикл, вложенные циклы, рекурсивный вызов или операцию деления диапазона. Если цикл выполняется n раз, его сложность O(n). Последовательные участки складываются, но в итоговой оценке оставляют самый быстро растущий член.

Например, если алгоритм делает n действий, затем ещё 3n действий и несколько постоянных операций, получается 4n + 7. В асимптотике это O(n), потому что множитель 4 и число 7 не меняют порядок роста.

Для вложенных циклов оценки перемножаются. Цикл на n шагов внутри цикла на n шагов даёт n × n = n², то есть O(n²). Если внутренний цикл выполняется только до i, общее число повторений равно 1 + 2 + … + n = n(n + 1) / 2, что также имеет сложность O(n²).

Разобранный пример

Рассмотрим поиск двух одинаковых элементов в массиве. Алгоритм сравнивает каждый элемент с каждым следующим. Нужно понять, сколько сравнений выполнится в худшем случае, если совпадений нет.

для i от 1 до n − 1
для j от i + 1 до n
если a[i] = a[j], вывести «да»
после циклов вывести «нет»

При i = 1 внутренний цикл делает n − 1 сравнений, при i = 2 — n − 2, и так далее. Получается сумма (n − 1) + (n − 2) + … + 1. Её можно записать как n(n − 1) / 2. Старший член — n², поэтому сложность алгоритма равна O(n²).

Память, кроме самого массива, почти не используется: нужны только индексы i и j. Дополнительная сложность по памяти — O(1). Если сначала отсортировать массив, а затем проверять соседние элементы, время можно уменьшить до O(n log n), но появится зависимость от выбранной сортировки.

Для закрепления можно решить похожий разбор в бесплатной практике в личном кабинете: там удобно проверять не только ответ, но и ход рассуждений.

Типичные ошибки и лучшие случаи

Первая ошибка — считать только одну итерацию цикла. Если цикл вложен, нужно учитывать все сочетания повторений. Вторая — путать O(n) и O(n²): два последовательных цикла дают O(n + n) = O(n), а два вложенных — O(n²).

Третья ошибка — забывать о худшем случае. Линейный поиск может сразу найти нужный элемент, но может проверить весь массив. Для оценки обычно рассматривают именно максимально возможное число действий, если условие задачи не просит средний или лучший случай.

Ещё одна ловушка: O(2n) и O(n) — один класс, а O(n²) и O(n) — разные. Также O(log n) не означает «всегда мало операций»: важно, что логарифмический рост значительно медленнее линейного при больших n.

Если хочешь потренироваться на экзаменационных формулировках, используй раздел для подготовки к ЕГЭ или материалы для ОГЭ, выбирая задания по своему уровню.

Что запомнить

Размер входа обозначают n, а сложность описывают порядком роста числа операций. O(1) не зависит от n, O(log n) растёт медленно, O(n) соответствует одному проходу, O(n log n) часто встречается у хороших сортировок, а O(n²) появляется при полном сравнении пар или двух вложенных циклах.

При анализе действуй по плану: найди размер данных, выдели циклы и рекурсию, посчитай повторения, упрости выражение и отдельно оцени дополнительную память. Постоянные слагаемые и множители отбрасывай только после определения главного растущего члена.

Следующий шаг — зарегистрируйся и реши 5 заданий бесплатно в личном кабинете. После каждого решения объясни себе, почему получилась именно такая оценка: это закрепляет способ мышления, а не только отдельную формулу.

Что означает запись O(1)?

Она означает постоянную сложность: число действий не меняется при увеличении размера входных данных. Например, обращение к элементу массива по известному индексу обычно выполняется за O(1).

Почему в O(n + n²) оставляют только O(n²)?

При больших n квадрат растёт быстрее линейного члена. Поэтому n² становится главным вкладом, а итоговую сложность записывают как O(n²).

Всегда ли два цикла означают O(n²)?

Нет. Если циклы идут последовательно, их сложности складываются: O(n) + O(n) = O(n). Квадратичная оценка обычно появляется, когда один цикл вложен в другой и оба зависят от n.

Как закрепить тему после разбора?

Реши несколько задач с циклами, выпиши для каждой размер входа и число повторений, а затем сравни свой разбор с правильным решением. Полезно отдельно потренировать последовательные и вложенные циклы.