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

Що означає, що операція виконується за час O(1)?

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

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

1. AСортування вставками
2. BСортування злиттям
3. CШвидке сортування (quicksort)
4. DСортування бульбашкою

Які три кроки алгоритму «розділяй і володарюй»?

1. AРозділити, підкорити, об'єднати
2. BВгадати, перевірити, повторити
3. CВідсортувати, знайти, повернути
4. DПрочитати, обчислити, записати

Яка часова складність обчислення n-го числа Фібоначчі за допомогою таблиці знизу вгору?

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

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

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

Нижня межа для сортування на основі порівнянь у найгіршому випадку становить:

1. AΩ(log n)
2. BΩ(n²)
3. CΩ(n)
4. DΩ(n log n)

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

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

Алгоритм Штрассена множить матриці, використовуючи 7 замість 8 рекурсивних множень блоків половинного розміру. Який його час виконання?

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