# Анализ алгоритмов: сложность и графы

> Учимся считать шаги алгоритма: O(1), O(log n), O(n) и O(n^2), трассируем формального исполнителя и проверяем графы через степени вершин.

**Информатика, 11 класс.** Урок бесплатного онлайн-самоучителя «ШкольныйГид». Обновлено: 2026-09-27.

Страница урока: https://shkolniygid.ru/informatika/11-klass/analiz-algoritmov-11/

Два ученика решают одну задачу: первый находит фамилию в списке перебором, второй — делением пополам. Оба получают верный ответ, но на списке из миллиона записей первый будет искать час, второй — долю секунды. Разница не в удаче, а в **сложности алгоритма** — в том, как растёт число шагов при росте данных. Анализ алгоритма отвечает на вопрос «что будет, когда данных станет много» до запуска программы.


### Сложность: считаем шаги


Сложность записывают в нотации **O большое**: в скобках — порядок роста. Доступ к элементу списка по индексу — O(1): сколько бы данных ни было, шаг один. Бинарный поиск по отсортированному списку — O(log n): каждое сравнение отбрасывает половину, миллиард элементов — около 30 шагов. Один проход по данным — O(n). Вложенные циклы, где для каждого элемента перебирают все остальные, — O(n в квадрате): пузырёк из 9 класса именно такой. Константы нотация скрывает: важен характер роста, а не секунды конкретного компьютера.


$$O(n^{2})$$

*Квадратичная сложность: цикл внутри цикла*


| Сложность | 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 в квадрате, и на миллионе элементов она не поместится ни в один школьный компьютер. Поэтому автор решения всегда смотрит на оба ресурса: сколько шагов и сколько памяти требуется по мере роста данных.


### Исполнители: строго по программе


**Формальный исполнитель** — объект, который выполняет команды из своей **системы команд** (СКИ) и ничего не понимает «между строк»: робот на поле, чертёжник, абстрактная машина. Он не исправит опечатку и не догадается о намерении — сделает ровно то, что записано. Поэтому программы на экзамене проверяют **трассировкой**: вручную протоколируют значение после каждой команды. Это скучно и надёжно, как таблица умножения.


**Трассировка: команды «прибавь 3» и «умножь на 2», программа 112**

1. Старт: число 2. Первая команда — прибавь 3: получаем 5.
2. Вторая команда снова прибавь 3: получаем 8.
3. Третья команда умножь на 2: получаем 16.
4. Ответ: 16. Записывай каждое значение — так не собьёшься.


> **Ловушка.** Порядок команд меняет результат: 2, потом прибавь 3 и умножь на 2 — это 10, а умножь на 2 и прибавь 3 — это 7. Трассируй по одной команде, а не «на глаз». Вторая ловушка: формальный исполнитель не умеет «примерно» — команда вне его СКИ или шаг в стену это ошибка программы, а не фантазия исполнителя.


### Графы: вершины, рёбра, степени


Схема дорог, друзей в соцсети, переходы между страницами — всё это **графы**: вершины и рёбра между ними. **Степень вершины** — число рёбер, которые в неё входят. Каждое ребро касается ровно двух вершин, поэтому сумма степеней всех вершин равна удвоенному числу рёбер — и всегда чётна. В полном графе из каждой вершины ведёт ребро в каждую, а деревом называют граф без циклов. Для дорог между пунктами граф часто задают таблицей, и задача «найти кратчайший путь» решается перебором маршрутов — в 9 классе вы это уже делали.


> **Совет.** Один проход по данным — O(n). Цикл внутри цикла — O(n в квадрате). Деление задачи пополам — O(log n). Два независимых цикла подряд дают O(n), а не O(n в квадрате): их шаги складываются, а не умножаются. Этой шпаргалки хватает на большинство задач.


### Разбор типовой задачи


Типовая задача: дана программа с вложенными циклами — сколько раз выполнится тело и какая у алгоритма сложность. Пусть s = 0, внешний цикл for i in range(4), внутри него for j in range(3), и тело делает s = s + 1. Спрашивают значение s и порядок роста числа шагов.


**Прогон вложенного цикла**

1. Внешний цикл повторяется 4 раза: i = 0, 1, 2, 3.
2. Внутренний цикл повторяется 3 раза на каждый внешний: j = 0, 1, 2.
3. Тело выполняется 4 умножить на 3 — 12 раз, значит s = 12.
4. Трассировка первого витка: i = 0, j идёт по значениям 0, 1, 2 — s выросло с 0 до 3.
5. Второй виток доводит s до 6, третий — до 9, четвёртый — до 12.
6. Сложность: при 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.
- Кратчайший путь по таблице дорог: выписывай маршруты целиком и складывай длины, не пропусти ни одного варианта.


*[Интерактив: Собери пары: понятие и его смысл — доступен на странице урока]*


*[Интерактив: Верно или нет? — доступен на странице урока]*


*[Интерактив: Вставь пропуски — доступен на странице урока]*


## Частые вопросы

### Что значит запись O(n^2)?

Это порядок роста: при удвоении данных время растёт примерно вчетверо. Константы запись скрывает — важно, как алгоритм масштабируется, а не секунды на конкретном компьютере.


### Почему формальный исполнитель не «догадывается»?

Он выполняет ровно команды из своей системы команд. Опечатка даёт не «почти правильный» результат, а другой — поэтому программу и проверяют трассировкой.


### Как быстро оценить сложность программы?

Посмотри на циклы: один проход — O(n), цикл внутри цикла — O(n^2), деление задачи пополам — O(log n). Два независимых цикла подряд остаются O(n).


### Что даёт сумма степеней вершин графа?

Удвоенное число рёбер: каждое ребро касается двух вершин. Приём помогает проверять себя в задачах на рукопожатия и графы дорог.


## Проверь себя (вопросы и ответы)

#### Вопрос 1: Алгоритм со сложностью O(n) делает порядка 500 шагов на списке из 500 элементов. Сколько шагов (по порядку) сделает алгоритм с O(n^2) на том же списке?
**Ответ:** 250000

*Пояснение: n в квадрате: 500 умножить на 500 — 250 000 шагов.*


#### Вопрос 2: Какая сложность у бинарного поиска в отсортированном списке из n элементов?
- ☐ O(1)
- ✅ O(log n)
- ☐ O(n)
- ☐ O(n^2)

*Пояснение: Каждое сравнение отбрасывает половину списка: понадобится порядка log n шагов.*


#### Вопрос 3: Два независимых цикла подряд по n элементов дают сложность O(n^2).
- ☐ Правда
- ✅ Неправда

*Пояснение: Их шаги складываются: 2n — это по-прежнему O(n). Умножение даёт вложенный цикл.*


#### Вопрос 4: В графе 4 ребра. Чему равна сумма степеней всех вершин?
**Ответ:** 8

*Пояснение: Сумма степеней равна удвоенному числу рёбер: 4 умножить на 2 — 8.*


#### Вопрос 5: Исполнитель умеет две команды: прибавь 3 и умножь на 2. Начальное число 1, программа: умножь на 2, прибавь 3, умножь на 2. Какое число получится в конце?
**Ответ:** 10

*Пояснение: 1 умножить на 2 — 2; 2 плюс 3 — 5; 5 умножить на 2 — 10.*


#### Вопрос 6: Сколько рёбер у полного графа с 5 вершинами (из каждой вершины ребро в каждую)?
- ☐ 8
- ✅ 10
- ☐ 20
- ☐ 25

*Пояснение: Каждая из 5 вершин соединена с 4 другими, и каждое ребро посчитано дважды: 5 умножить на 4 пополам — 10.*


#### Вопрос 7: Если сумма степеней всех вершин графа равна 20, то в графе 10 рёбер.
- ✅ Правда
- ☐ Неправда

*Пояснение: Сумма степеней равна удвоенному числу рёбер: 20 пополам — 10 рёбер.*


#### Вопрос 8: Соедини факт о сложности или графе с его числовым значением.
- 1024 элемента, бинарный поиск — около 10 сравнений
- 1000 элементов, O(n) — 1000 шагов
- 1000 элементов, O(n^2) — 1 000 000 шагов
- полный граф на 5 вершинах — 10 рёбер

*Пояснение: Логарифм от миллиона — около 20, а квадратичный рост умножает данные сами на себя: отсюда и гигантская разница в шагах.*


## Тренажёр

На [странице тренажёра](https://shkolniygid.ru/informatika/11-klass/analiz-algoritmov-11/trenazher/) — 6 типов задач с бесконечными вариантами чисел, проверкой ответа и разбором каждого шага.