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

Що таке алгоритм повного перебору?

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

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

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

Що з наведеного зростає найповільніше зі збільшенням n?

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

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

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

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

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

Яке твердження про рекурсивну функцію без досяжного базового випадку правильне?

1. AВона викликає себе, доки не переповниться стек викликів
2. BВона автоматично повертає 0
3. CКомпілятор завжди перетворює її на цикл, що безпечно завершується
4. DВона виконується за час O(1)

Яка різниця між нерозв'язною задачею та практично нерозв'язною?

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

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

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