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

Який клас складності зростає найшвидше для великих n?

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

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

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

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

1. AДинамічне програмування
2. BПовний перебір
3. CЖадібний вибір
4. D«Розділяй і володарюй»

Яке жадібне правило в задачі про вибір заявок (activity selection) завжди дає максимальну кількість заявок, що не перекриваються?

1. AСпершу обрати найкоротшу заявку
2. BОбрати заявку, що починається найраніше
3. CОбрати заявку, що закінчується найраніше, а потім повторити із сумісними
4. DСпершу обрати заявку з найменшою кількістю перекриттів, а потім повторити із сумісними

Часова складність наївного рекурсивного обчислення чисел Фібоначчі (fib(n) = fib(n−1) + fib(n−2)) є:

1. AЕкспоненційною
2. BЛогарифмічною
3. CСталою
4. DЛінійною

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

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

Чому бінарний пошук не дає часу O(log n) на однозв'язному списку?

1. AПорівняння вузлів зв'язного списку повільніші
2. BЗв'язні списки неможливо сортувати
3. CБінарному пошуку потрібно щонайменше вдвічі більше пам'яті
4. DЩоб дістатися середнього елемента, потрібно O(n) кроків, бо немає прямого доступу за індексом

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

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