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

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

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

Чего бинарный поиск требует от входных данных?

1. AМассив должен содержать только положительные числа
2. BДлина массива должна быть степенью двойки
3. CВ массиве должно быть не более 1000 элементов
4. DМассив должен быть отсортирован

Что из этого растёт медленнее всего при больших n?

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

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

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

Какой алгоритм находит кратчайшие пути из одного источника в графе с неотрицательными весами рёбер?

1. AВо всех случаях требуется алгоритм Беллмана–Форда
2. BАлгоритм Краскала
3. CПоиск в глубину (DFS)
4. DАлгоритм Дейкстры

Поиск в ширину в невзвешенном графе находит:

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

Сортировка вставками работает за O(n) на отсортированном входе. Противоречит ли это нижней оценке Ω(n log n) для сортировки сравнениями?

1. AДа, но только для массивов короче 100
2. BНет, нижняя оценка относится к худшему случаю по всем входам, а не к каждому входу
3. CДа, значит, нижняя оценка неверна
4. DНет, потому что сортировка вставками не является сортировкой сравнениями

По основной теореме (master theorem) решением T(n) = 8T(n/2) + O(n²) является:

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