6.2. Практикум

Примечание

При выполнении заданий используйте заготовки решений: -> Репозиторий.

Подробнее: см. Цикл выполнения и защиты заданий.

6.2.1. Оценка сложности алгоритмов

Для задач 6.2.1-6.2.7 ответьте на следующие вопросы:

  1. Что выполняет приведенная функция?

  2. Какова вычислительная сложность алгоритма (наихудшая оценка, \(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. Сравнение сложности алгоритмов

Для каждой задачи ниже:

  1. Реализуйте требуемые способы решения.

  2. Укажите наихудшую вычислительную (асимптотическую) сложность каждого из способов в строке документации.

  3. Сравните способы решения, сопоставив их асимптотические и временные сложности (устно).

№ 6.2.8

Дан список случайных чисел. Определить значения минимального и максимального элементов списка.

№ 6.2.9

По вылету из аэропорта осуществляется паспортный контроль: сотрудник пограничной службы выполняет проверку в специальном приложении.

Для каждого паспорта в приложении хранится (количество записей большое):

  • номер: 7-значное число;

  • отметка о допуске: может / не может пересекать границу.

Предполагается, что проверка осуществляется путем ввода номера паспорта, после чего приложение должно выдать отметку о допуске (отсутствие паспорта в приложении аналогично отсутствие возможности вылета).

Реализуйте функцию проверки допуска к вылету.

№ 6.2.10

Дана информация о клиентах банка (идентификационный номер и сумма активов). Реализуйте поиск топ-3 клиентов по размеру активов.