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

Який час виконання сортування підрахунком для n цілих чисел у діапазоні від 0 до k?

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

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

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

Цикл починається з i = 1 і подвоює i на кожній ітерації, доки i > n. Скільки ітерацій він виконує?

1. AБлизько n / 2
2. BБлизько n²
3. CБлизько n
4. DБлизько log₂ n

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

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

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

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

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

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

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

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

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

1. AАлгоритм Дейкстри
2. BАлгоритм Флойда–Воршелла
3. CАлгоритм Краскала
4. DАлгоритм Прима, що починає з однієї вершини