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

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

1. AСортування злиттям
2. BСортування вставками
3. CСортування бульбашкою
4. DШвидке сортування (quicksort)

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

1. AОчікуваний час на випадкових вхідних даних розміру n
2. BЧас на найменших вхідних даних
3. CЧас на повільному комп'ютері
4. DМаксимальний час на всіх вхідних даних розміру n

Що таке алгоритм повного перебору?

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

Нижня межа для сортування на основі порівнянь у найгіршому випадку становить:

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

Яка часова складність алгоритму Беллмана–Форда на графі з V вершинами та E ребрами?

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

Ви один раз сортуєте масив із n елементів, а потім відповідаєте на k запитів про належність бінарним пошуком. Яка загальна вартість?

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

Для якого варіанта задачі про рюкзак жадібне правило «брати предмети в порядку цінності на одиницю ваги» завжди дає оптимальну відповідь?

1. AДля жодного варіанта
2. BДля рюкзака 0/1, де предмети завжди потрібно брати цілими
3. CДля обох варіантів
4. DДля неперервного (дробового) рюкзака, де предмети можна ділити

Чи належить 2²ⁿ до O(2ⁿ)?

1. AТак, бо обидві функції експоненційні
2. BНі, бо 2²ⁿ = 4ⁿ, а 4ⁿ / 2ⁿ = 2ⁿ зростає необмежено
3. CНі, бо 2²ⁿ зростає повільніше, ніж 2ⁿ
4. DТак, бо сталі множники в показнику степеня в нотації «велике O» завжди ігноруються