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

Доступ к элементу массива по индексу занимает:

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

Какую стратегию проектирования использует сортировка слиянием?

1. AЖадный выбор
2. B«Разделяй и властвуй»
3. CДинамическое программирование
4. DПолный перебор

Какая нотация описывает верхнюю границу роста?

1. AОмега-малое
2. BТета-большое
3. CO-большое
4. DОмега-большое

Что означает, что задача обладает оптимальной подструктурой?

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

Какое утверждение о рекурсивной функции без достижимого базового случая верно?

1. AОна автоматически возвращает 0
2. BКомпилятор всегда превращает её в цикл, который безопасно завершается
3. CОна продолжает вызывать себя, пока не переполнится стек вызовов
4. DОна работает за время O(1)

Каково решение рекуррентного соотношения T(n) = T(n − 1) + O(n)?

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

Почему любой поиск в отсортированном массиве, основанный на сравнениях, требует в худшем случае Ω(log n) сравнений?

1. AБинарный поиск — единственный возможный алгоритм, и ему нужно log₂ n сравнений
2. BКаждый элемент нужно сравнить хотя бы один раз
3. CКаждое сравнение занимает логарифмическое время
4. DДерево решений с n возможными исходами должно иметь глубину не менее log₂ n

В чём разница между неразрешимой и трудноразрешимой задачей?

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