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

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

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

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

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

Що таке алгоритм?

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

Чому основу логарифма в «великому O» зазвичай не вказують, як-от в O(log n)?

1. AЛогарифми завжди округлюють до цілих
2. BОснова має значення лише для малих n
3. CЛогарифми з різними основами відрізняються лише сталим множником
4. DУсі логарифми в інформатиці мають основу 10, тож вона мається на увазі

Жадібний алгоритм:

1. AНа кожному кроці робить локально найкращий вибір
2. BЗавжди дає оптимальний розв'язок
3. CВикористовує лише рекурсію
4. DПеребирає всі можливі розв'язки

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

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

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

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

Алгоритм Штрассена множить матриці, використовуючи 7 замість 8 рекурсивних множень блоків половинного розміру. Який його час виконання?

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