Оценка сложности алгоритма
Оценка сложности алгоритма позволяет заранее понять, сколько действий выполнит программа при размере входных данных \(n\). На экзамене важно не запускать алгоритм для всех возможных значений, а выразить число операций формулой, учесть повторения циклов и сравнить полученные оценки.
Зачем оценивать алгоритм
Алгоритм получает входные данные: число, массив, строку или другой объект. Размер входа обычно обозначают \(n\). Например, для массива из \(n\) элементов размером входа считается количество элементов, а для числа иногда используют количество его цифр или разрядов.
При анализе считают не время в секундах, а количество элементарных операций: присваиваний, сравнений, арифметических действий, обращений к элементу массива. Такая оценка не зависит от компьютера и языка программирования. В школьных задачах чаще всего требуется найти точное число повторений команды или сравнить количество итераций.
Сложность алгоритма — зависимость количества выполняемых операций от размера входных данных \(n\). Если учитывается количество операций, говорят о временной сложности; если объём используемой памяти — о пространственной сложности.
Перед подсчётом полезно составить трассировочную таблицу для нескольких небольших значений \(n\). Она помогает увидеть закономерность, но окончательный ответ нужно получить из структуры алгоритма. При анализе циклов пригодится понятие инварианта: инвариант цикла помогает понять, что сохраняется после каждой итерации.
Базовые правила подсчёта
Если команды выполняются последовательно, их количества складываются. Если один фрагмент выполняется \(a(n)\) раз, а другой \(b(n)\) раз, общее число операций равно \(a(n)+b(n)\).
Если команда находится внутри цикла, её число выполнений равно числу итераций цикла. Для цикла от 1 до \(n\) это обычно \(n\) раз. Важно отличать тело цикла от проверки условия: в цикле с условием проверка может выполняться на одну единицу чаще, чем тело.
| Конструкция | Число выполнений (типичный случай) | Оценка |
|---|---|---|
| Одна команда | 1 | \(1\) |
| Последовательные фрагменты | \(a(n)+b(n)\) | складываются |
| Цикл от 1 до \(n\) | \(n\) итераций | \(n\) |
| Два вложенных цикла по \(n\) | \(n\cdot n\) | \(n^2\) |
| Цикл, где переменная удваивается | \(1,2,4,\dots\) до \(n\) | около \(\log_2 n\) |
Для вложенных циклов количества итераций перемножаются, если число повторений внутреннего цикла не зависит от внешней переменной. Если оно зависит от неё, нужно записать сумму. Например, при внутреннем цикле от 1 до \(i\) общее число выполнений равно \(1+2+\dots+n\).
При сравнении роста функций для больших \(n\) обычно оставляют слагаемое, растущее быстрее всего. Например, \(3n^2+5n+7\) имеет квадратичный рост: главное слагаемое — \(3n^2\), а порядок роста обозначают как \(O(n^2)\).
Линейная, квадратичная и логарифмическая сложность
Линейный алгоритм выполняет примерно пропорциональное \(n\) число действий: \(T(n)=an+b\). Пример — последовательный просмотр всех элементов массива. Линейный поиск в худшем случае проверяет каждый элемент, поэтому имеет линейную сложность.
Квадратичный алгоритм обычно содержит два вложенных цикла. Он выполняет около \(n^2\) операций и быстро становится медленным при увеличении размера входа. Так работают многие простые алгоритмы обработки всех пар элементов.
Логарифмическая сложность появляется, когда на каждом шаге размер задачи уменьшается в несколько раз. Например, при делении диапазона пополам число шагов примерно равно \(\log_2 n\). На этом принципе основан двоичный поиск.
При больших \(n\) константное время лучше логарифмического, логарифмическое — линейного, линейное — квадратичного, а квадратичное — экспоненциального. Сравнивают именно рост, а не только значения при одном маленьком \(n\).
Сколько раз выполнится команда внутри двух вложенных циклов, каждый из которых повторяется \(n\) раз?
Разобранный пример: подсчёт операций
Рассмотрим фрагмент алгоритма. Переменная \(s\) накапливает сумму чисел от 1 до \(n\). Нужно определить, сколько раз выполняется операция сложения и как зависит общее число действий от \(n\).
1s := 0\nfor i := 1 to n do\n s := s + i\nend for
Строка \(s:=0\) выполняется один раз. Тело цикла выполняется \(n\) раз. В каждой итерации есть одно сложение и одно присваивание. Если считать также начальное присваивание, получаем \(1+2n\) операций этого типа. Если учитывать проверки границы цикла, добавится ещё примерно \(n+1\) сравнений. Точная формула зависит от принятой модели подсчёта, но порядок роста во всех случаях линейный: \(O(n)\).
Теперь изменим тело: пусть для каждого \(i\) выполняется внутренний цикл от 1 до \(i\). Тогда при \(i=1\) будет 1 операция, при \(i=2\) — 2, и так далее. Поэтому общее число операций равно сумме \(1+2+\dots+n\), то есть \(\frac{n(n+1)}2\), а порядок роста — \(O(n^2)\).
Лучший, средний и худший случаи
Один и тот же алгоритм может выполнять разное число операций в зависимости от входных данных. В лучшем случае нужный элемент найден сразу. В худшем случае его приходится искать до конца или элемент отсутствует. Средний случай описывает типичное поведение при заданном распределении входов.
Например, при последовательном поиске в массиве из \(n\) элементов первый элемент находится за одну проверку, последний — за \(n\) проверок. Если элемент с равной вероятностью может находиться на любой позиции, среднее число проверок равно \(\frac{n+1}{2}\). Но асимптотически и средний, и худший случаи являются линейными: \(O(n)\).
Сначала определите, какая переменная задаёт размер входа. Затем найдите число повторений самого внутреннего действия, учтите условия выхода из цикла и только после этого упростите формулу. Если требуется сравнить алгоритмы, подставьте одно и то же значение \(n\) или сравните их порядки роста.
Частые ошибки
1. Складывать числа итераций вложенных циклов вместо умножения. 2. Считать цикл по условию выполненным ровно столько раз, сколько выполнено тело: последняя проверка часто происходит после последней итерации. 3. Забывать, что шаг \(i:=2i\) даёт логарифмическое, а не линейное число итераций. 4. Сравнивать только коэффициенты и игнорировать степень: при больших \(n\) алгоритм \(n^2\) хуже алгоритма \(1000n\). 5. Путать число операций с числом строк программы. 6. Считать рекурсивные вызовы, не анализируя глубину рекурсии и число ветвлений.
Для рекурсивных алгоритмов полезно проследить стек рекурсивных вызовов и записать, сколько новых вызовов создаётся на каждом уровне. При разборе состояния программы можно использовать страницу состояние исполнителя, особенно если задача связана с пошаговым выполнением команд.
Самопроверка
Проверьте себя
Главное
- Размер входа обозначают \(n\), а сложность выражает зависимость числа операций от \(n\).
- Для последовательных фрагментов сложности складываются, для независимых вложенных циклов — перемножаются.
- Сумма \(1+2+\dots+n\) равна \(\frac{n(n+1)}2\) и имеет квадратичный порядок \(O(n^2)\).
- При сравнении больших входов используют порядок роста: \(O(1)\), \(O(\log n)\), \(O(n)\), \(O(n^2)\) и далее.
- Всегда различайте лучшее, среднее и худшее число операций и заранее определяйте, что именно считается операцией.