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

Як працює сортування вибором?

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

Що з наведеного зростає найповільніше зі збільшенням n?

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

Задачу зазвичай називають практично розв'язною (tractable), якщо:

1. AЇї можна розв'язати за поліноміальний час
2. BЇї можна розв'язати лише перебором усіх можливостей
3. CЇї можна розв'язати за сталий час
4. DВона не має розв'язку

Функція виконує один цикл із n ітерацій, а потім окремо ще один цикл із n ітерацій. Яка її часова складність?

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

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

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

Як алгоритм Прима будує мінімальне кістякове дерево?

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

Множення Карацуби задовольняє T(n) = 3T(n/2) + O(n). Який розв'язок?

1. AΘ(n log n)
2. BΘ(n³)
3. CΘ(n²)
4. DΘ(n^{log₂ 3}), близько n^1,585

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

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