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

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

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

Як працює сортування вибором?

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

Яка оцінка «велике O» для 3n² + 5n + 2?

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

Жадібний алгоритм:

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

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

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

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

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

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

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

Яке визначення класу NP правильне?

1. AЗадачі, що не є поліноміальними
2. BЗадачі, які не може розв'язати жоден алгоритм
3. CЗадачі розпізнавання, відповіді «так» для яких можна перевірити за поліноміальний час за наявності сертифіката
4. DЗадачі, які неможливо розв'язати за поліноміальний час