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

Яку стратегію проєктування використовує сортування злиттям?

1. AПовний перебір
2. B«Розділяй і володарюй»
3. CЖадібний вибір
4. DДинамічне програмування

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

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

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

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

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

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

Яка часова складність множення двох матриць n × n стандартним потрійним циклом?

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

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

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

Які дві речі треба показати, щоб довести, що задача розпізнавання X є NP-повною?

1. AX належить до P, і X зводиться до SAT
2. BX зводиться до задачі з P, і X належить до NP
3. CX не має поліноміального алгоритму, і X розв'язна
4. DX належить до NP, і відома NP-повна задача зводиться до X за поліноміальний час

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

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