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

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

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

Какова временная сложность сортировки слиянием в худшем случае?

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

Какова временна́я сложность сортировки вставками в лучшем случае, на уже отсортированном массиве?

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

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

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

Вы один раз сортируете массив из n элементов, а затем отвечаете на k запросов о принадлежности бинарным поиском. Какова общая стоимость?

1. AO(k n log n)
2. BO(nk)
3. CO(n + k)
4. DO(n log n + k log n)

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

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

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

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

Какая из этих задач выполнимости, как известно, решается за полиномиальное время?

1. A3-SAT, где в каждом дизъюнкте ровно три литерала
2. BОбщая SAT для формул в конъюнктивной нормальной форме
3. C2-SAT, где в каждом дизъюнкте не более двух литералов
4. DВыполнимость схем