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

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

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

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

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

Що таке мемоізація?

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

Динамічне програмування корисне, коли задача має:

1. AПерекривні підзадачі та оптимальну підструктуру
2. BЛише випадкові вхідні дані
3. CЖодних підзадач, тож її можна розв'язати за один крок
4. DОдин цикл

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

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

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

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

Яка часова складність: for i = 1 to n: for (j = i; j ≤ n; j = j + i) виконати роботу O(1)?

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

Яке твердження про позначення «мале o» правильне?

1. An = o(n²), але n не є o(n)
2. Bn = o(n), бо кожна функція є «мале o» від самої себе
3. C2n = o(n), бо 2n зростає повільно
4. Dn² = o(n)