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

Что означает, что операция выполняется за время O(1)?

1. AВремя её работы не растёт с размером входных данных
2. BОна всегда занимает ровно одну секунду
3. CОна обрабатывает ровно один элемент за секунду времени работы
4. DЕё можно выполнить только один раз

Что такое алгоритм полного перебора (brute force)?

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

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

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

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

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

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

1. AНа массиве, все элементы которого различны
2. BНа уже отсортированном массиве
3. CНа массиве длины 2
4. DНа массиве в случайном порядке

Какой алгоритм сортировки является устойчивым?

1. AПирамидальная сортировка
2. BСортировка выбором (типичная версия)
3. CБыстрая сортировка (типичная версия на месте)
4. DСортировка слиянием

Принадлежит ли 2²ⁿ классу O(2ⁿ)?

1. AНет, потому что 2²ⁿ = 4ⁿ, а 4ⁿ / 2ⁿ = 2ⁿ растёт неограниченно
2. BДа, потому что постоянные множители в показателе в O большом всегда игнорируются
3. CНет, потому что 2²ⁿ растёт медленнее 2ⁿ
4. DДа, потому что обе функции экспоненциальны

Как алгоритм Беллмана–Форда обнаруживает цикл отрицательного веса, достижимый из источника?

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