6.2. Практикум¶
Примечание
При выполнении заданий используйте заготовки решений: ->
Репозиторий.
Подробнее: см. Цикл выполнения и защиты заданий.
6.2.1. Оценка сложности алгоритмов¶
Для задач 6.2.1-6.2.7 ответьте на следующие вопросы:
Что выполняет приведенная функция?
Какова вычислительная сложность алгоритма (наихудшая оценка, \(O\)-нотацию)?
Ответы необходимо указать в строке документации с пометкой «Алгоритм» и «Сложность» соответственно. Сложность - один из вариантов:
O(1), O(N), O(log(N)), O(N log(N)) или O(N^2).
считая, что \(N\) - размер входных данных.
№№ 6.2.1 - 6.2.7
См. заготовки.
6.2.2. Сравнение сложности алгоритмов¶
Для каждой задачи ниже:
Реализуйте требуемые способы решения.
Укажите наихудшую вычислительную (асимптотическую) сложность каждого из способов в строке документации.
Сравните способы решения, сопоставив их асимптотические и временные сложности (устно).
№ 6.2.8
Дан список случайных чисел. Определить значения минимального и максимального элементов списка.
№ 6.2.9
По вылету из аэропорта осуществляется паспортный контроль: сотрудник пограничной службы выполняет проверку в специальном приложении.
Для каждого паспорта в приложении хранится (количество записей большое):
номер: 7-значное число;
отметка о допуске: может / не может пересекать границу.
Предполагается, что проверка осуществляется путем ввода номера паспорта, после чего приложение должно выдать отметку о допуске (отсутствие паспорта в приложении аналогично отсутствие возможности вылета).
Реализуйте функцию проверки допуска к вылету.
№ 6.2.10
Дана информация о клиентах банка (идентификационный номер и сумма активов). Реализуйте поиск топ-3 клиентов по размеру активов.