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

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

1. A1 секунду
2. B4 секунди
3. C2 секунди
4. D8 секунд

Яка нотація описує верхню межу зростання?

1. AМале омега
2. BВелике Омега
3. CВелике O
4. DВелике Тета

Що таке мемоізація?

1. AАвтоматичне перетворення рекурсії на рівносильний цикл, щоб стек викликів не був потрібен
2. BЗбереження результатів викликів функції, щоб повторні виклики отримували відповідь із пам'яті
3. CНаписання коментарів біля кожного рядка коду
4. DЗвільнення пам'яті після повернення з функції

Який алгоритм знаходить найкоротші шляхи з одного джерела в графі з невід'ємними вагами ребер?

1. AАлгоритм Дейкстри
2. BПошук у глибину (DFS)
3. CУ всіх випадках потрібен алгоритм Беллмана–Форда
4. DАлгоритм Краскала

Скільки пам'яті стека використовує проста рекурсивна функція факторіала fact(n) = n × fact(n − 1)?

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

Розв'язком рекурентного співвідношення T(n) = 2T(n/2) + O(n) є:

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

Алгоритм динамічного програмування Гелда–Карпа точно розв'язує задачу комівояжера. Який його час виконання для n міст?

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

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

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