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

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

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

Що означає, що операція виконується за час O(1)?

1. AЇї час виконання не зростає з розміром вхідних даних
2. BВона обробляє рівно один елемент за секунду часу виконання
3. CВона завжди триває рівно одну секунду
4. DЇї можна виконати лише один раз

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

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

Який алгоритм сортування є стійким?

1. AСортування вибором (типова версія)
2. BСортування злиттям
3. CШвидке сортування (типова версія на місці)
4. DПірамідальне сортування

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

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

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

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

Алгоритм Штрассена множить матриці, використовуючи 7 замість 8 рекурсивних множень блоків половинного розміру. Який його час виконання?

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

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

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