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

Який час виконання сортування підрахунком для n цілих чисел у діапазоні від 0 до k?

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

Яку складність зазвичай має алгоритм із двома вкладеними циклами, кожен із яких виконується n разів?

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

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

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

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

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

Чому динамічне програмування не дає реального пришвидшення для сортування злиттям?

1. AДинамічне програмування працює лише на задачах про графи, а не на масивах
2. BСортування злиттям не має рекурсивної структури
3. CЙого підзадачі не перекриваються, тож нічого використати повторно
4. DСортування злиттям уже має складність O(n)

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

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

Яка часова складність побудови бінарної купи з n невідсортованих елементів висхідним методом (bottom-up)?

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

Який прийом забезпечує очікуваний час роботи O(n log n) для швидкого сортування на будь-яких вхідних даних?

1. AВибір завжди першого елемента
2. BЗастосування рекурсії лише до лівої частини
3. CВибір опорного елемента випадково з рівномірним розподілом
4. DСортування вхідних даних перед запуском швидкого сортування