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

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

1. A8 секунд
2. B1 секунду
3. C4 секунди
4. D2 секунди

Що таке базовий випадок рекурсивної функції?

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

Скільки додаткової пам'яті використовує стандартне сортування злиттям на основі масиву?

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

Скільки рівнів має рекурсія сортування злиттям для масиву з n елементів?

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

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

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

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

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

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

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

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

1. AАлгоритм Краскала
2. BАлгоритм Флойда–Воршелла
3. CАлгоритм Дейкстри
4. DАлгоритм Прима, що починає з однієї вершини