Робочий аркуш «Алгоритми та складність» з відповідями

Який із цих часів виконання є поліноміальним?

1. AO(n³)
2. BO(n!)
3. CO(nⁿ)
4. DO(2ⁿ)

Що таке рекурсія?

1. AФункція, яка викликає саму себе для менших вхідних даних
2. BЦикл, який ніколи не закінчується
3. CМетод сортування
4. DТип структури даних

Алгоритм O(n) працює 3 секунди для n = 1 мільйон. Приблизно скільки він працюватиме для n = 2 мільйони?

1. A9 секунд
2. B6 секунд
3. C12 секунд
4. D3 секунди

Яка часова складність множення двох матриць n × n стандартним потрійним циклом?

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

Який розв'язок рекурентного співвідношення T(n) = 2T(n − 1) + O(1)?

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

Яке твердження про рекурсивну функцію без досяжного базового випадку правильне?

1. AВона автоматично повертає 0
2. BКомпілятор завжди перетворює її на цикл, що безпечно завершується
3. CВона викликає себе, доки не переповниться стек викликів
4. DВона виконується за час O(1)

За основною теоремою (master theorem) розв'язком T(n) = 8T(n/2) + O(n²) є:

1. AΘ(n³)
2. BΘ(n log n)
3. CΘ(n² log n)
4. DΘ(n²)

Що випливало б, якби хтось знайшов поліноміальний алгоритм для однієї NP-повної задачі?

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