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

Що таке алгоритм повного перебору?

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

Яка нотація описує верхню межу зростання?

1. AМале омега
2. BВелике Тета
3. CВелике O
4. DВелике Омега

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

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

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

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

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

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

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

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

Чому алгоритм Дейкстри може давати неправильні результати, коли деякі ваги ребер від'ємні?

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

Множення Карацуби задовольняє T(n) = 3T(n/2) + O(n). Який розв'язок?

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