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

Какую сложность обычно имеет алгоритм с двумя вложенными циклами, каждый из которых выполняется n раз?

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

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

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

Пространственная сложность измеряет:

1. AМесто на диске, занимаемое файлом программы после компиляции
2. BОбъём памяти, необходимый алгоритму по мере роста входных данных
3. CФизический размер компьютера
4. DКоличество строк кода

Что означает, что задача обладает оптимальной подструктурой?

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

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

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

Какова временна́я сложность: for i = 1 to n: for j = 1 to i: выполнить работу O(1)?

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

Что последовало бы, если бы кто-то нашёл полиномиальный алгоритм для одной NP-полной задачи?

1. AПроблема остановки стала бы разрешимой
2. BТолько эта одна задача перешла бы в P
3. CВсе алгоритмы с экспоненциальным временем сразу стали бы работать за линейное время
4. DКаждую задачу из NP можно было бы решить за полиномиальное время, то есть P = NP

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

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