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

Який час виконання сортування підрахунком для n цілих чисел у діапазоні від 0 до k?

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

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

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

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

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

Чому основу логарифма в «великому O» зазвичай не вказують, як-от в O(log n)?

1. AУсі логарифми в інформатиці мають основу 10, тож вона мається на увазі
2. BОснова має значення лише для малих n
3. CЛогарифми з різними основами відрізняються лише сталим множником
4. DЛогарифми завжди округлюють до цілих

Нижня межа для сортування на основі порівнянь у найгіршому випадку становить:

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

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

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

Яке твердження про вибір k-го найменшого елемента невідсортованого масиву правильне?

1. AQuickselect працює за O(log n) у найгіршому випадку, бо рекурсивно переходить лише в один бік від опорного елемента
2. BВибір завжди потребує Ω(n log n), бо вимагає сортування
3. CQuickselect працює за очікуваний час O(n), а метод медіани медіан гарантує O(n) у найгіршому випадку
4. DВибір можливий лише за O(n²)

Як алгоритм Беллмана–Форда виявляє цикл від'ємної ваги, досяжний із джерела?

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