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

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

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

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

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

Час виконання алгоритму — O(n). Як називається таке зростання?

1. AКвадратичне
2. BЛінійне
3. CЛогарифмічне
4. DСтале

Яка часова складність множення двох матриць n × n стандартним потрійним циклом?

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

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

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

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

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

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

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

Що встановила теорема Кука–Левіна?

1. AПроблема зупинки нерозв'язна
2. BКожну задачу з NP можна розв'язати за експоненційний час
3. CЗадача виконуваності булевих формул (SAT) є NP-повною
4. DP не дорівнює NP