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

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

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

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

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

Какова временна́я сложность поиска наибольшего значения в неотсортированном массиве из n чисел?

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

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

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

Какова временна́я сложность: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

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

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

Проблема остановки показывает, что:

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

Задача является NP-полной, если она:

1. AНеразрешима
2. BПринадлежит NP и любая задача из NP сводится к ней за полиномиальное время
3. CЛежит вне NP, но сложнее всех задач NP, как проблема остановки
4. DРешается за полиномиальное время