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

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

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

Цикл починається з i = 1 і подвоює i на кожній ітерації, доки i > n. Скільки ітерацій він виконує?

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

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

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

Маючи монети номіналом 1, 3 і 4 та суму 6, скільки монет використовує жадібний метод «спершу найбільша монета» порівняно з оптимумом?

1. AЖадібний використовує 2 монети; оптимум — 2
2. BЖадібний використовує 3 монети; оптимум — 2
3. CЖадібний використовує 4 монети; оптимум — 3
4. DЖадібний використовує 3 монети; оптимум — 3

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

1. AЛінійною
2. BЛогарифмічною
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)

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

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

Проблема зупинки показує, що:

1. AСлід уникати циклів
2. BЖоден алгоритм не може для кожної програми та вхідних даних визначити, чи зупиниться вона
3. CКожна програма врешті-решт зупиняється
4. DДеякі програми працюють швидше на швидших комп'ютерах, тож зупинка залежить від апаратного забезпечення