Анализ алгоритмов: сложность и графы — тренажёр
Тренировка по теме «Анализ алгоритмов: сложность и графы»: задачи с меняющимися числами, мгновенная проверка, подсказка и подробный разбор к каждой. Ниже — шпаргалка по теме, разобранные примеры и ответы на частые вопросы.
Тренировка
0/81 Алгоритм перебирает все пары элементов списка из 17 элементов. Сколько шагов он сделает? Считай порядок n в квадрате.
Выбери ответ и нажми «Проверить». Подсказка рядом — пользоваться не стыдно.
Разбор примеров из тренажёра
22 задач из пула этого тренажёра с полной логикой решения: условие, подсказка, как решать и ответ. В самом тренажёре числа в каждой задаче обновляются от раунда к раунду — принцип решения остаётся тем же.
Пример 1. Алгоритм перебирает все пары элементов списка из 21 элементов. Сколько шагов он сделает? Считай порядок n в квадрате.
Подсказка. Каждый элемент сравнивается с каждым.
Как решать. Вложенные циклы: 21 умножить на 21 шагов.
Ответ: 441
Пример 2. В графе 4 рёбер. Чему равна сумма степеней всех его вершин?
Подсказка. Ребро всегда касается двух вершин.
Как решать. Каждое ребро добавляет единицу двум вершинам: 4 умножить на 2.
Ответ: 8
Пример 3. Исполнитель получил число 4 и программу: прибавь 6, затем умножь на 2. Какое число он выведет?
Подсказка. Действия выполняются по порядку записи.
Как решать. Сначала 4 плюс 6, затем результат удваивается.
Ответ: 20
Пример 4. Исполнитель стартует с нуля и повторяет команду «прибавь 7» ровно 7 раз. Какое число получится?
Подсказка. Повторение сложения — это умножение.
Как решать. 7 раз по 7: 7 умножить на 7.
Ответ: 49
Пример 5. Какая сложность у линейного поиска по неотсортированному списку из n элементов?
Подсказка. Поиск идёт по элементам подряд.
Как решать. В худшем случае проверяются все n элементов — один проход по списку.
Ответ: O(n)
Пример 6. Сумма степеней всех вершин любого графа — всегда чётное число.
Как решать. Каждое ребро вносит по единице в степень двух вершин, поэтому сумма степеней равна удвоенному числу рёбер.
Ответ: Верно
Пример 7. Алгоритм перебирает все пары элементов списка из 11 элементов. Сколько шагов он сделает? Считай порядок n в квадрате.
Подсказка. Каждый элемент сравнивается с каждым.
Как решать. Вложенные циклы: 11 умножить на 11 шагов.
Ответ: 121
Пример 8. В графе 10 рёбер. Чему равна сумма степеней всех его вершин?
Подсказка. Ребро всегда касается двух вершин.
Как решать. Каждое ребро добавляет единицу двум вершинам: 10 умножить на 2.
Ответ: 20
Пример 9. Исполнитель получил число 3 и программу: прибавь 4, затем умножь на 2. Какое число он выведет?
Подсказка. Действия выполняются по порядку записи.
Как решать. Сначала 3 плюс 4, затем результат удваивается.
Ответ: 14
Пример 10. Исполнитель стартует с нуля и повторяет команду «прибавь 6» ровно 5 раз. Какое число получится?
Подсказка. Повторение сложения — это умножение.
Как решать. 5 раз по 6: 5 умножить на 6.
Ответ: 30
Пример 11. Какая сложность у линейного поиска по неотсортированному списку из n элементов?
Подсказка. Поиск идёт по элементам подряд.
Как решать. В худшем случае проверяются все n элементов — один проход по списку.
Ответ: O(n)
Пример 12. Алгоритм перебирает все пары элементов списка из 18 элементов. Сколько шагов он сделает? Считай порядок n в квадрате.
Подсказка. Каждый элемент сравнивается с каждым.
Как решать. Вложенные циклы: 18 умножить на 18 шагов.
Ответ: 324
Пример 13. В графе 8 рёбер. Чему равна сумма степеней всех его вершин?
Подсказка. Ребро всегда касается двух вершин.
Как решать. Каждое ребро добавляет единицу двум вершинам: 8 умножить на 2.
Ответ: 16
Пример 14. Исполнитель стартует с нуля и повторяет команду «прибавь 5» ровно 15 раз. Какое число получится?
Подсказка. Повторение сложения — это умножение.
Как решать. 15 раз по 5: 15 умножить на 5.
Ответ: 75
Пример 15. Какая сложность у линейного поиска по неотсортированному списку из n элементов?
Подсказка. Поиск идёт по элементам подряд.
Как решать. В худшем случае проверяются все n элементов — один проход по списку.
Ответ: O(n)
Пример 16. Алгоритм перебирает все пары элементов списка из 24 элементов. Сколько шагов он сделает? Считай порядок n в квадрате.
Подсказка. Каждый элемент сравнивается с каждым.
Как решать. Вложенные циклы: 24 умножить на 24 шагов.
Ответ: 576
Пример 17. В графе 11 рёбер. Чему равна сумма степеней всех его вершин?
Подсказка. Ребро всегда касается двух вершин.
Как решать. Каждое ребро добавляет единицу двум вершинам: 11 умножить на 2.
Ответ: 22
Пример 18. Исполнитель получил число 5 и программу: прибавь 9, затем умножь на 2. Какое число он выведет?
Подсказка. Действия выполняются по порядку записи.
Как решать. Сначала 5 плюс 9, затем результат удваивается.
Ответ: 28
Пример 19. Исполнитель стартует с нуля и повторяет команду «прибавь 3» ровно 14 раз. Какое число получится?
Подсказка. Повторение сложения — это умножение.
Как решать. 14 раз по 3: 14 умножить на 3.
Ответ: 42
Пример 20. В графе 12 рёбер. Чему равна сумма степеней всех его вершин?
Подсказка. Ребро всегда касается двух вершин.
Как решать. Каждое ребро добавляет единицу двум вершинам: 12 умножить на 2.
Ответ: 24
Пример 21. Исполнитель получил число 2 и программу: прибавь 8, затем умножь на 2. Какое число он выведет?
Подсказка. Действия выполняются по порядку записи.
Как решать. Сначала 2 плюс 8, затем результат удваивается.
Ответ: 20
Пример 22. Исполнитель стартует с нуля и повторяет команду «прибавь 6» ровно 13 раз. Какое число получится?
Подсказка. Повторение сложения — это умножение.
Как решать. 13 раз по 6: 13 умножить на 6.
Ответ: 78
Вопросы для повторения темы
Контрольные вопросы по «Анализ алгоритмов: сложность и графы» с верными ответами и пояснениями — проверь себя до запуска тренажёра.
Вопрос 1. Алгоритм со сложностью O(n) делает порядка 500 шагов на списке из 500 элементов. Сколько шагов (по порядку) сделает алгоритм с O(n^2) на том же списке?
Ответ: 250000
Пояснение. n в квадрате: 500 умножить на 500 — 250 000 шагов.
Вопрос 2. Какая сложность у бинарного поиска в отсортированном списке из n элементов?
Ответ: O(log n)
Пояснение. Каждое сравнение отбрасывает половину списка: понадобится порядка 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 вершинами (из каждой вершины ребро в каждую)?
Ответ: 10
Пояснение. Каждая из 5 вершин соединена с 4 другими, и каждое ребро посчитано дважды: 5 умножить на 4 пополам — 10.
Вопрос 7. Если сумма степеней всех вершин графа равна 20, то в графе 10 рёбер.
Ответ: Верно
Пояснение. Сумма степеней равна удвоенному числу рёбер: 20 пополам — 10 рёбер.
Вопрос 8. Соедини факт о сложности или графе с его числовым значением.
Пояснение. Логарифм от миллиона — около 20, а квадратичный рост умножает данные сами на себя: отсюда и гигантская разница в шагах.
Настройте ритм перед экзаменом: задание дня по информатике — новое каждый день.