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

Чому дорівнює log₂ 1024?

1. A10
2. B512
3. C12
4. D32

Яку складність зазвичай має алгоритм із двома вкладеними циклами, кожен із яких виконується n разів?

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

Доступ до елемента масиву за індексом займає:

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

Чи правильно казати, що алгоритм O(n²) є також O(n³)?

1. AНі, бо «велике O» завжди має вказувати точну швидкість зростання функції
2. BТак, бо «велике O» — верхня межа, а n² зростає не швидше, ніж n³
3. CТак, але лише якщо n менше за 100
4. DНі, бо для великих n n³ менше за n²

Часова складність наївного рекурсивного обчислення чисел Фібоначчі (fib(n) = fib(n−1) + fib(n−2)) є:

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

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

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

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

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

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

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