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

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

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

Яка оцінка «велике O» для 3n² + 5n + 2?

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

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

1. AO(V × E)
2. BO(V + E)
3. CO(V²)
4. DO(E log V)

Що вимірює амортизований аналіз?

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

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

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

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

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

Яка оцінка для log(n!) правильна?

1. AΘ(log n)
2. BΘ(n)
3. CΘ(n²)
4. DΘ(n log n)

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

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