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

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

1. AO(log n)
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Фізичний розмір комп'ютера

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

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

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

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

Функція виконує один цикл із n ітерацій, а потім окремо ще один цикл із n ітерацій. Яка її часова складність?

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

Яке визначення класу NP правильне?

1. AЗадачі, які не може розв'язати жоден алгоритм
2. BЗадачі, що не є поліноміальними
3. CЗадачі, які неможливо розв'язати за поліноміальний час
4. DЗадачі розпізнавання, відповіді «так» для яких можна перевірити за поліноміальний час за наявності сертифіката

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

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