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

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

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

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

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

Що описує час виконання алгоритму в найгіршому випадку?

1. AОчікуваний час на випадкових вхідних даних розміру n
2. BЧас на найменших вхідних даних
3. CЧас на повільному комп'ютері
4. DМаксимальний час на всіх вхідних даних розміру n

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

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

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

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

Яка часова складність алгоритму Беллмана–Форда на графі з V вершинами та E ребрами?

1. AO(V + E)
2. BO(V × E)
3. CO(E log V)
4. DO(V³ × E)

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

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

Яке твердження про позначення «мале o» правильне?

1. An = o(n), бо кожна функція є «мале o» від самої себе
2. Bn² = o(n)
3. Cn = o(n²), але n не є o(n)
4. D2n = o(n), бо 2n зростає повільно