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

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

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

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

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

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

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

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

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

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

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

Чи правильно казати, що алгоритм O(n²) є також O(n³)?

1. AТак, але лише якщо n менше за 100
2. BНі, бо «велике O» завжди має вказувати точну швидкість зростання функції
3. CТак, бо «велике O» — верхня межа, а n² зростає не швидше, ніж n³
4. DНі, бо для великих n n³ менше за n²

Задача є NP-повною, якщо вона:

1. AЛежить поза NP, але складніша за всі задачі NP, як-от проблема зупинки
2. BРозв'язна за поліноміальний час
3. CНалежить до NP і будь-яка задача з NP зводиться до неї за поліноміальний час
4. DНерозв'язна

Яка часова складність побудови бінарної купи з n невідсортованих елементів висхідним методом (bottom-up)?

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