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

Що означає f(n) = Θ(g(n))?

1. Af зростає строго швидше, ніж g
2. Bf зростає з тією самою швидкістю, що й g, обмежена зверху й знизу сталими кратними g
3. Cf зростає строго повільніше, ніж g
4. Df завжди менша за g для кожного n, тож g обмежує її зверху, але ніколи знизу

Як працює сортування вибором?

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

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

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

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

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

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

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

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

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

Що встановила теорема Кука–Левіна?

1. AКожну задачу з NP можна розв'язати за експоненційний час
2. BP не дорівнює NP
3. CЗадача виконуваності булевих формул (SAT) є NP-повною
4. DПроблема зупинки нерозв'язна

Алгоритм Штрассена множить матриці, використовуючи 7 замість 8 рекурсивних множень блоків половинного розміру. Який його час виконання?

1. AΘ(n² log n)
2. BΘ(n³)
3. CΘ(n^{log₂ 7}), близько n^2,81
4. DΘ(n²)