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

Що описує час виконання в середньому випадку?

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

Як називається зростання O(2ⁿ)?

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

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

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

Що обчислює алгоритм Флойда–Воршелла і як швидко?

1. AНайкоротші шляхи між усіма парами вершин за O(V³)
2. BНайкоротші шляхи від однієї початкової вершини до всіх інших за O(V + E)
3. CМінімальне кістякове дерево за O(E log V)
4. DТопологічний порядок за O(V²)

Маючи монети номіналом 1, 3 і 4 та суму 6, скільки монет використовує жадібний метод «спершу найбільша монета» порівняно з оптимумом?

1. AЖадібний використовує 2 монети; оптимум — 2
2. BЖадібний використовує 3 монети; оптимум — 2
3. CЖадібний використовує 4 монети; оптимум — 3
4. DЖадібний використовує 3 монети; оптимум — 3

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

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

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

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

Чи належить 2²ⁿ до O(2ⁿ)?

1. AНі, бо 2²ⁿ = 4ⁿ, а 4ⁿ / 2ⁿ = 2ⁿ зростає необмежено
2. BТак, бо обидві функції експоненційні
3. CТак, бо сталі множники в показнику степеня в нотації «велике O» завжди ігноруються
4. DНі, бо 2²ⁿ зростає повільніше, ніж 2ⁿ