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

Що описує час виконання в середньому випадку?

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

Які три кроки алгоритму «розділяй і володарюй»?

1. AРозділити, підкорити, об'єднати
2. BПрочитати, обчислити, записати
3. CВгадати, перевірити, повторити
4. DВідсортувати, знайти, повернути

Скільки додаткової пам'яті використовує стандартне сортування злиттям на основі масиву?

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

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

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

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

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

Нижня межа для сортування на основі порівнянь у найгіршому випадку становить:

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

Задача про рюкзак 0/1, розв'язана динамічним програмуванням, потребує O(nW) часу. Чому це називають псевдополіноміальним часом?

1. AТому що він працює лише для W = 0
2. BТому що n завжди мале
3. CТому що алгоритм рандомізований, а його час роботи змінюється для кожних вхідних даних
4. DW — число, тому час експоненційний відносно кількості бітів, використаних для запису W

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

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