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

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

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

Що бінарний пошук вимагає від вхідних даних?

1. AМасив має містити лише додатні числа
2. BМасив має бути відсортованим
3. CДовжина масиву має бути степенем двійки
4. DМасив має містити не більше 1000 елементів

Що таке мемоізація?

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

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

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

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

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

Що вимірює амортизований аналіз?

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

Який прийом забезпечує очікуваний час роботи O(n log n) для швидкого сортування на будь-яких вхідних даних?

1. AСортування вхідних даних перед запуском швидкого сортування
2. BВибір завжди першого елемента
3. CЗастосування рекурсії лише до лівої частини
4. DВибір опорного елемента випадково з рівномірним розподілом

Як класифікують задачу комівояжера?

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