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

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

1. A3 секунди
2. B12 секунд
3. C6 секунд
4. D9 секунд

Що означає f(n) = Θ(g(n))?

1. Af завжди менша за g для кожного n, тож g обмежує її зверху, але ніколи знизу
2. Bf зростає строго швидше, ніж g
3. Cf зростає строго повільніше, ніж g
4. Df зростає з тією самою швидкістю, що й g, обмежена зверху й знизу сталими кратними g

Яка часова складність сортування злиттям у найгіршому випадку?

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

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

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

Динамічне програмування корисне, коли задача має:

1. AОдин цикл
2. BЛише випадкові вхідні дані
3. CПерекривні підзадачі та оптимальну підструктуру
4. DЖодних підзадач, тож її можна розв'язати за один крок

Яка часова складність стандартного алгоритму динамічного програмування для найдовшої спільної підпослідовності рядків довжиною m і n?

1. AO(mn log n)
2. BO(mn)
3. CO(m + n)
4. DO(2^m+n)

Що треба зробити, щоб показати, що нова задача X є NP-складною?

1. AПоказати, що X можна перевірити за поліноміальний час
2. BЗвести X до відомої NP-складної задачі за поліноміальний час
3. CЗвести відому NP-складну задачу до X за поліноміальний час
4. DПоказати, що X не має поліноміального алгоритму для малих вхідних даних

Яке визначення класу NP правильне?

1. AЗадачі розпізнавання, відповіді «так» для яких можна перевірити за поліноміальний час за наявності сертифіката
2. BЗадачі, що не є поліноміальними
3. CЗадачі, які неможливо розв'язати за поліноміальний час
4. DЗадачі, які не може розв'язати жоден алгоритм