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

Просторова складність вимірює:

1. AОбсяг пам'яті, потрібний алгоритму зі зростанням вхідних даних
2. BФізичний розмір комп'ютера
3. CКількість рядків коду
4. DМісце на диску, яке займає файл програми після компіляції

Яке позначення описує нижню межу зростання?

1. AO (велике O)
2. Bo (мале o)
3. CΘ (велике Тета)
4. DΩ (велике Омега)

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

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

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

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

Який алгоритм сортування є стійким?

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

Яке жадібне правило в задачі про вибір заявок (activity selection) завжди дає максимальну кількість заявок, що не перекриваються?

1. AСпершу обрати найкоротшу заявку
2. BОбрати заявку, що закінчується найраніше, а потім повторити із сумісними
3. CСпершу обрати заявку з найменшою кількістю перекриттів, а потім повторити із сумісними
4. DОбрати заявку, що починається найраніше

Яка різниця між нерозв'язною задачею та практично нерозв'язною?

1. AДля нерозв'язної задачі немає алгоритму для всіх вхідних даних; для практично нерозв'язної він є, але надто повільний
2. BНерозв'язні задачі належать до NP, а практично нерозв'язні — до P
3. CОбидва терміни означають, що задача взагалі не має алгоритму
4. DПрактично нерозв'язні задачі не може розв'язати жоден алгоритм, а нерозв'язні лише потребують експоненційного часу

Множення Карацуби задовольняє T(n) = 3T(n/2) + O(n). Який розв'язок?

1. AΘ(n²)
2. BΘ(n^{log₂ 3}), близько n^1,585
3. CΘ(n³)
4. DΘ(n log n)