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

Время работы алгоритма O(n). Как называется такой рост?

1. AЛогарифмический
2. BЛинейный
3. CКвадратичный
4. DПостоянный

Как называется рост O(2ⁿ)?

1. AПолиномиальный
2. BЛогарифмический
3. CЭкспоненциальный
4. DЛинейный

Что такое базовый случай рекурсивной функции?

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

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

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

Нижняя граница для сортировки сравнениями в худшем случае равна:

1. AΩ(n log n)
2. BΩ(n)
3. CΩ(n²)
4. DΩ(log n)

Как алгоритм Прима строит минимальное остовное дерево?

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

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

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

Какое определение класса P верно?

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