Алгоритмы и сложность: лист заданий с ответами

Какова временная сложность линейного поиска в неотсортированном массиве из n элементов (в худшем случае)?

1. AO(n²)
2. BO(1)
3. CO(n)
4. DO(log n)

Цикл начинается с i = 1 и удваивает i на каждой итерации, пока i > n не станет истинным. Сколько итераций он выполнит?

1. AОколо log₂ n
2. BОколо n / 2
3. CОколо n
4. DОколо n²

Сколько дополнительной памяти использует стандартная сортировка слиянием на массивах?

1. AO(n²)
2. BO(log n)
3. CO(1)
4. DO(n)

Почему многие библиотечные процедуры сортировки переходят на сортировку вставками для очень маленьких подмассивов?

1. AУ сортировки вставками малые накладные расходы, и она быстра на маленьких или почти отсортированных входах
2. BСортировка вставками использует меньше памяти, чем любой другой алгоритм сортировки, на больших входах
3. CСортировка вставками имеет сложность O(n log n) в худшем случае
4. DРекурсивные алгоритмы не справляются с массивами меньше 10 элементов

Динамическое программирование полезно, когда у задачи есть:

1. AВообще никаких подзадач, поэтому её можно решить за один шаг
2. BТолько случайные входные данные
3. CОдин цикл
4. DПерекрывающиеся подзадачи и оптимальная подструктура

Сколько уровней у рекурсии сортировки слиянием для массива из n элементов?

1. AОколо log₂ n
2. BОколо n / 2
3. CОколо n
4. DОколо √n

Какой приём обеспечивает ожидаемое время работы O(n log n) для быстрой сортировки на любых входных данных?

1. AПрименение рекурсии только к левой части
2. BСортировка входных данных перед запуском быстрой сортировки
3. CВыбор опорного элемента случайно с равномерным распределением
4. DВыбор всегда первого элемента

Какова временная сложность построения двоичной кучи из n неотсортированных элементов восходящим методом (bottom-up)?

1. AO(n²)
2. BO(n log n)
3. CO(n)
4. DO(log n)