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

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

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

Що бінарний пошук вимагає від вхідних даних?

1. AМасив має бути відсортованим
2. BМасив має містити не більше 1000 елементів
3. CМасив має містити лише додатні числа
4. DДовжина масиву має бути степенем двійки

Що таке алгоритм?

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

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

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

Який розв'язок рекурентного співвідношення T(n) = T(n − 1) + O(n)?

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

Чому основу логарифма в «великому O» зазвичай не вказують, як-от в O(log n)?

1. AЛогарифми з різними основами відрізняються лише сталим множником
2. BОснова має значення лише для малих n
3. CУсі логарифми в інформатиці мають основу 10, тож вона мається на увазі
4. DЛогарифми завжди округлюють до цілих

Як співвідносяться n! і 2ⁿ для великих n?

1. An! є O(n²)
2. B2ⁿ зростає швидше, ніж n!
3. Cn! зростає швидше, ніж 2ⁿ
4. DВони зростають з однаковою швидкістю

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

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