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

Який час виконання сортування підрахунком для n цілих чисел у діапазоні від 0 до k?

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

Як називається зростання O(2ⁿ)?

1. AЛогарифмічне
2. BЛінійне
3. CЕкспоненційне
4. DПоліноміальне

Задачу зазвичай називають практично розв'язною (tractable), якщо:

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

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

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

Чому основу логарифма в «великому O» зазвичай не вказують, як-от в O(log n)?

1. AОснова має значення лише для малих n
2. BУсі логарифми в інформатиці мають основу 10, тож вона мається на увазі
3. CЛогарифми завжди округлюють до цілих
4. DЛогарифми з різними основами відрізняються лише сталим множником

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

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

Які часові та просторові витрати обчислення n-го числа Фібоначчі циклом, що зберігає лише два останні значення?

1. AO(2ⁿ) часу та O(1) пам'яті
2. BO(log n) часу та O(n) пам'яті
3. CO(n) часу та O(n) пам'яті
4. DO(n) часу та O(1) пам'яті

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

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