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

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

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

Що означає f(n) = Θ(g(n))?

1. Af зростає строго швидше, ніж g
2. Bf зростає з тією самою швидкістю, що й g, обмежена зверху й знизу сталими кратними g
3. Cf завжди менша за g для кожного n, тож g обмежує її зверху, але ніколи знизу
4. Df зростає строго повільніше, ніж g

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

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

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

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

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

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

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

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

Яка часова складність: for i = 1 to n: for (j = i; j ≤ n; j = j + i) виконати роботу O(1)?

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

Що встановила теорема Кука–Левіна?

1. AПроблема зупинки нерозв'язна
2. BКожну задачу з NP можна розв'язати за експоненційний час
3. CЗадача виконуваності булевих формул (SAT) є NP-повною
4. DP не дорівнює NP