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

Цикл починається з i = 1 і подвоює i на кожній ітерації, доки i > n. Скільки ітерацій він виконує?

1. AБлизько log₂ n
2. BБлизько n / 2
3. CБлизько n
4. DБлизько n²

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

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

Яка часова складність бінарного пошуку у відсортованому масиві?

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

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

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

Чи правильно казати, що алгоритм O(n²) є також O(n³)?

1. AНі, бо для великих n n³ менше за n²
2. BТак, але лише якщо n менше за 100
3. CТак, бо «велике O» — верхня межа, а n² зростає не швидше, ніж n³
4. DНі, бо «велике O» завжди має вказувати точну швидкість зростання функції

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

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

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

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

Яке твердження про вибір k-го найменшого елемента невідсортованого масиву правильне?

1. AQuickselect працює за очікуваний час O(n), а метод медіани медіан гарантує O(n) у найгіршому випадку
2. BВибір завжди потребує Ω(n log n), бо вимагає сортування
3. CВибір можливий лише за O(n²)
4. DQuickselect працює за O(log n) у найгіршому випадку, бо рекурсивно переходить лише в один бік від опорного елемента