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

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

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

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

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

Алгоритм O(n) працює 3 секунди для n = 1 мільйон. Приблизно скільки він працюватиме для n = 2 мільйони?

1. A12 секунд
2. B6 секунд
3. C3 секунди
4. D9 секунд

Функція виконує один цикл із n ітерацій, а потім окремо ще один цикл із n ітерацій. Яка її часова складність?

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

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

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

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

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

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

1. AЩонайбільше в log n разів більше за мінімум
2. BНевідомої якості порівняно з оптимумом
3. CЗавжди мінімальне вершинне покриття
4. DЩонайбільше вдвічі більше за мінімальне вершинне покриття

Топологічне сортування можливе лише для:

1. AГрафів із від'ємними вагами
2. BОрієнтованих ациклічних графів
3. CПовних графів
4. DНеорієнтованих графів