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

Що описує час виконання в середньому випадку?

1. AОчікуваний час за заданого розподілу вхідних даних розміру n
2. BСереднє значення між часами виконання в найкращому й найгіршому випадках
3. CЧас для вхідних даних середньої довжини
4. DЧас на найпоширенішому комп'ютері

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

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

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

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

Яка часова складність стандартного алгоритму динамічного програмування для найдовшої спільної підпослідовності рядків довжиною m і n?

1. AO(m + n)
2. BO(2^m+n)
3. CO(mn log n)
4. DO(mn)

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

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

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

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

Чому алгоритм Дейкстри може давати неправильні результати, коли деякі ваги ребер від'ємні?

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

Топологічне сортування можливе лише для:

1. AГрафів із від'ємними вагами
2. BПовних графів
3. CНеорієнтованих графів
4. DОрієнтованих ациклічних графів