Анализ алгоритмов: сложность и графы
Учимся считать шаги алгоритма: O(1), O(log n), O(n) и O(n^2), трассируем формального исполнителя и проверяем графы через степени вершин.
Два ученика решают одну задачу: первый находит фамилию в списке перебором, второй — делением пополам. Оба получают верный ответ, но на списке из миллиона записей первый будет искать час, второй — долю секунды. Разница не в удаче, а в сложности алгоритма — в том, как растёт число шагов при росте данных. Анализ алгоритма отвечает на вопрос «что будет, когда данных станет много» до запуска программы.
Сложность: считаем шаги
Сложность записывают в нотации O большое: в скобках — порядок роста. Доступ к элементу списка по индексу — O(1): сколько бы данных ни было, шаг один. Бинарный поиск по отсортированному списку — O(log n): каждое сравнение отбрасывает половину, миллиард элементов — около 30 шагов. Один проход по данным — O(n). Вложенные циклы, где для каждого элемента перебирают все остальные, — O(n в квадрате): пузырёк из 9 класса именно такой. Константы нотация скрывает: важен характер роста, а не секунды конкретного компьютера.
| Сложность | n = 10 | n = 1000 | Пример |
|---|---|---|---|
| O(1) | 1 | 1 | доступ по индексу |
| O(log n) | около 3 | около 10 | бинарный поиск |
| O(n) | 10 | 1000 | линейный поиск |
| O(n^2) | 100 | 1 000 000 | пузырёк, перебор пар |
Считаем шаги в числах
Закрепим разницу между сложностями числами. Пусть компьютер выполняет миллиард простых операций в секунду. Алгоритм с O(n) на списке из 1000 элементов сделает тысячу шагов — миллионную долю секунды. Алгоритм с O(n^2) на том же списке сделает миллион шагов — тоже мгновенно, 0,001 секунды. Но возьмём 10 000 элементов: 100 миллионов шагов, десятая доля секунды. А миллион элементов — это уже 10 в двенадцатой степени шагов, около семнадцати минут ожидания. Данные выросли в тысячу раз, а время — в миллион: в этом и есть характер квадратичного роста.
Удвоение данных — быстрая проверка сложности без всякого кода. O(n): время удвоится. O(n^2): время вырастет вчетверо. O(log n): добавится один шаг, ведь 2 в двадцатой степени — примерно миллион, а 2 в двадцать первой — уже два миллиона. Поэтому бинарный поиск даже по миллиарду записей укладывается в тридцать сравнений, и именно так устроены справочники внутри реальных программ.
Сложность важна и для памяти, а не только для времени. Если алгоритм хранит копию списка, памяти нужно вдвое больше исходных данных. Если он заводит таблицу всех пар элементов — памяти нужно порядка n в квадрате, и на миллионе элементов она не поместится ни в один школьный компьютер. Поэтому автор решения всегда смотрит на оба ресурса: сколько шагов и сколько памяти требуется по мере роста данных.
Исполнители: строго по программе
Формальный исполнитель — объект, который выполняет команды из своей системы команд (СКИ) и ничего не понимает «между строк»: робот на поле, чертёжник, абстрактная машина. Он не исправит опечатку и не догадается о намерении — сделает ровно то, что записано. Поэтому программы на экзамене проверяют трассировкой: вручную протоколируют значение после каждой команды. Это скучно и надёжно, как таблица умножения.
- Старт: число 2. Первая команда — прибавь 3: получаем 5.
- Вторая команда снова прибавь 3: получаем 8.
- Третья команда умножь на 2: получаем 16.
- Ответ: 16. Записывай каждое значение — так не собьёшься.
Графы: вершины, рёбра, степени
Схема дорог, друзей в соцсети, переходы между страницами — всё это графы: вершины и рёбра между ними. Степень вершины — число рёбер, которые в неё входят. Каждое ребро касается ровно двух вершин, поэтому сумма степеней всех вершин равна удвоенному числу рёбер — и всегда чётна. В полном графе из каждой вершины ведёт ребро в каждую, а деревом называют граф без циклов. Для дорог между пунктами граф часто задают таблицей, и задача «найти кратчайший путь» решается перебором маршрутов — в 9 классе вы это уже делали.
Разбор типовой задачи
Типовая задача: дана программа с вложенными циклами — сколько раз выполнится тело и какая у алгоритма сложность. Пусть s = 0, внешний цикл for i in range(4), внутри него for j in range(3), и тело делает s = s + 1. Спрашивают значение s и порядок роста числа шагов.
- Внешний цикл повторяется 4 раза: i = 0, 1, 2, 3.
- Внутренний цикл повторяется 3 раза на каждый внешний: j = 0, 1, 2.
- Тело выполняется 4 умножить на 3 — 12 раз, значит s = 12.
- Трассировка первого витка: i = 0, j идёт по значениям 0, 1, 2 — s выросло с 0 до 3.
- Второй виток доводит s до 6, третий — до 9, четвёртый — до 12.
- Сложность: при n повторах внешнего и m внутреннего число шагов равно их произведению — это O(n^2), когда оба растут вместе.
Граф дорог: перебираем маршруты
Задача о кратчайшем пути в школьном варианте решается перебором. Между пунктами А, Б, В, Г и Д дороги: А—Б длиной 3, А—В длиной 5, Б—Г длиной 4, В—Г длиной 1 и Г—Д длиной 2. Нужен самый короткий путь из А в Д. Выпишем все маршруты через Г: А—Б—Г—Д стоит 3 + 4 + 2 = 9, а А—В—Г—Д стоит 5 + 1 + 2 = 8. Ответ 8: короче не бывает, других дорог в графе нет.
Дороги между пунктами на экзамене обычно задают таблицей: на пересечении строки и столбца стоит длина ребра или прочерк. Прежде чем перебирать маршруты, проверь таблицу рукой: сумма степеней вершин должна быть чётной, а каждое ребро — видно в двух клетках сразу. Такой самоконтроль занимает полминуты и спасает от потерянной дороги — самой частой ошибки в этих задачах.
Ещё одно классическое применение суммы степеней — задача о рукопожатиях. Семь друзей пожали руки друг другу: каждый пожал руку шести остальным, значит сумма степеней равна 7 умножить на 6 — 42, а рукопожатий вдвое меньше — 21. Проверка через полный граф: рёбер 7 умножить на 6 и пополам — снова 21. Приём «посчитай степени и раздели пополам» избавляет от нудного перебора пар вручную.
Дерево: граф-минимум и связность
Связным называют граф, в котором от любой вершины можно добраться до любой другой. Если связность пропала, граф распадается на куски — компоненты связности: две деревни без единой дороги между ними живут в разных компонентах. Самый экономный связный граф — дерево: у него нет ни одного цикла, а рёбер ровно n минус 1. Добавь ребро — появится цикл, убери — граф развалится на части. Поэтому деревья и называют графом-минимумом.
Деревья окружают тебя в программировании: файловая система компьютера — дерево папок и файлов, турнирная сетка чемпионата — дерево игр, меню настроек — дерево пунктов. На экзамене дерево чаще всего появляется в вопросах про число рёбер: запомни формулу n минус 1, и такие задания решаются в одну строку. Например, у дерева из 12 вершин ровно 11 рёбер — независимо от его формы.
Словарь урока
- Нотация O большое#
- запись порядка роста времени работы алгоритма
- Трассировка#
- пошаговая запись значений переменных по ходу программы
- Система команд#
- полный набор команд, которые умеет выполнять исполнитель
- Вложенные циклы#
- цикл внутри цикла: числа шагов перемножаются
- Полный граф#
- граф, в котором каждая вершина соединена с каждой
- Дерево#
- связный граф без циклов
Как это спрашивают на ЕГЭ
В блоке анализа алгоритмов экзамен проверяет три умения: посчитать шаги программы, оценить сложность по коду и поработать с графом. Все три тренируются одинаково — прогоном на бумаге. Типовые формулировки перечислены ниже.
- Сколько раз выполнится тело вложенного цикла: перемножь число повторов внешнего и внутреннего.
- Какая сложность у алгоритма: один проход — O(n), цикл в цикле — O(n^2), деление пополам — O(log n).
- Трассировка исполнителя: выписывай значение после каждой команды, включая стартовое.
- Число рёбер полного графа: для 5 вершин это 10, для 4 вершин — 6.
- Кратчайший путь по таблице дорог: выписывай маршруты целиком и складывай длины, не пропусти ни одного варианта.
Один проход по данным — это сложность , вложенные циклы дают , а сумма степеней всех вершин графа равна числа рёбер.
Банк слов
Проверь себя
Клавиши 1–9 выбирают вариант, Enter — «Проверить»
1 Алгоритм со сложностью O(n) делает порядка 500 шагов на списке из 500 элементов. Сколько шагов (по порядку) сделает алгоритм с O(n^2) на том же списке?
2 Какая сложность у бинарного поиска в отсортированном списке из n элементов?
3 Два независимых цикла подряд по n элементов дают сложность O(n^2).
4 В графе 4 ребра. Чему равна сумма степеней всех вершин?
5 Исполнитель умеет две команды: прибавь 3 и умножь на 2. Начальное число 1, программа: умножь на 2, прибавь 3, умножь на 2. Какое число получится в конце?
6 Сколько рёбер у полного графа с 5 вершинами (из каждой вершины ребро в каждую)?
7 Если сумма степеней всех вершин графа равна 20, то в графе 10 рёбер.
8 Соедини факт о сложности или графе с его числовым значением.
Нажми на элемент слева, затем на его пару справа. Повторное нажатие отменяет связь.
Было понятно? Скажи — так мы видим, какие темы переписать.
Частые вопросы
Что значит запись O(n^2)?
Это порядок роста: при удвоении данных время растёт примерно вчетверо. Константы запись скрывает — важно, как алгоритм масштабируется, а не секунды на конкретном компьютере.
Почему формальный исполнитель не «догадывается»?
Он выполняет ровно команды из своей системы команд. Опечатка даёт не «почти правильный» результат, а другой — поэтому программу и проверяют трассировкой.
Как быстро оценить сложность программы?
Посмотри на циклы: один проход — O(n), цикл внутри цикла — O(n^2), деление задачи пополам — O(log n). Два независимых цикла подряд остаются O(n).
Что даёт сумма степеней вершин графа?
Удвоенное число рёбер: каждое ребро касается двух вершин. Приём помогает проверять себя в задачах на рукопожатия и графы дорог.