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

Яка часова складність сортування вставками в найкращому випадку, на вже відсортованому масиві?

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

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

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

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

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

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

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

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

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

Який алгоритм знаходить найкоротші шляхи з одного джерела в графі з невід'ємними вагами ребер?

1. AАлгоритм Дейкстри
2. BУ всіх випадках потрібен алгоритм Беллмана–Форда
3. CАлгоритм Краскала
4. DПошук у глибину (DFS)

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

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

Алгоритм динамічного програмування Гелда–Карпа точно розв'язує задачу комівояжера. Який його час виконання для n міст?

1. AO(n³)
2. BO(n!)
3. CO(n² 2ⁿ)
4. DO(2^n²)