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

Що бінарний пошук вимагає від вхідних даних?

1. AДовжина масиву має бути степенем двійки
2. BМасив має містити лише додатні числа
3. CМасив має містити не більше 1000 елементів
4. DМасив має бути відсортованим

Яка часова складність пошуку в глибину на графі, збереженому у вигляді списків суміжності?

1. AO(E log V)
2. BO(V²)
3. CO(V + E)
4. DO(V × E)

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

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

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

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

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

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

Пошук у ширину в незваженому графі знаходить:

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

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

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

Який час виконання алгоритму Дейкстри з бінарною купою на графі з V вершинами та E ребрами?

1. AO(V × E)
2. BO((V + E) log V)
3. CO(V³)
4. DO(V + E)