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

Яка часова складність бінарного пошуку у відсортованому масиві?

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

Що таке алгоритм?

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

Просторова складність вимірює:

1. AОбсяг пам'яті, потрібний алгоритму зі зростанням вхідних даних
2. BМісце на диску, яке займає файл програми після компіляції
3. CКількість рядків коду
4. DФізичний розмір комп'ютера

Скільки пам'яті стека використовує проста рекурсивна функція факторіала fact(n) = n × fact(n − 1)?

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

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

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

Яка часова складність обчислення n-го числа Фібоначчі за допомогою таблиці знизу вгору?

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

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

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

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

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