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

Доступ до елемента масиву за індексом займає:

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

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

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

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

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

Яке твердження про рекурсивну функцію без досяжного базового випадку правильне?

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

Динамічне програмування корисне, коли задача має:

1. AЛише випадкові вхідні дані
2. BЖодних підзадач, тож її можна розв'язати за один крок
3. CОдин цикл
4. DПерекривні підзадачі та оптимальну підструктуру

Розв'язком рекурентного співвідношення T(n) = 2T(n/2) + O(n) є:

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

Чому пошук у геш-таблиці в середньому має складність O(1), а в найгіршому випадку — O(n)?

1. AКлючі спершу потрібно відсортувати
2. BБагато ключів через колізії можуть потрапити в один і той самий кошик
3. CГеш-функції повільні
4. DДоступ до масивів має складність O(n)

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

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