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

Що з наведеного зростає найповільніше зі збільшенням n?

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

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

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

Алгоритм O(n²) працює 1 секунду для n = 1000. Приблизно скільки він працюватиме для n = 2000?

1. A8 секунд
2. B1 секунду
3. C2 секунди
4. D4 секунди

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

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

Який алгоритм знаходить найкоротші шляхи з одного джерела в графі з невід'ємними вагами ребер?

1. AПошук у глибину (DFS)
2. BАлгоритм Краскала
3. CАлгоритм Дейкстри
4. DУ всіх випадках потрібен алгоритм Беллмана–Форда

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

1. AO(log n)
2. BO(n²)
3. CO(n log 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) у найгіршому випадку, бо рекурсивно переходить лише в один бік від опорного елемента

За основною теоремою (master theorem) розв'язком T(n) = 8T(n/2) + O(n²) є:

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