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

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

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

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

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

Задачу обычно называют практически разрешимой (tractable), если:

1. AЕё можно решить за полиномиальное время
2. BЕё можно решить за постоянное время
3. CУ неё нет решения
4. DЕё можно решить только перебором всех возможностей

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

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

Временная сложность наивного рекурсивного вычисления чисел Фибоначчи (fib(n) = fib(n−1) + fib(n−2)) является:

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

Быстрая сортировка всегда берёт в качестве опорного первый элемент. На каком входе проявляется её поведение в худшем случае?

1. AНа массиве, все элементы которого различны
2. BНа массиве в случайном порядке
3. CНа массиве длины 2
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)

Какой алгоритм находит минимальное остовное дерево, многократно добавляя самое дешёвое ребро, не образующее цикла?

1. AАлгоритм Краскала
2. BАлгоритм Прима, начинающий с одной вершины
3. CАлгоритм Флойда–Уоршелла
4. DАлгоритм Дейкстры