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

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

1. AОчікуваний час на випадкових вхідних даних розміру n
2. BЧас на повільному комп'ютері
3. CМаксимальний час на всіх вхідних даних розміру n
4. DЧас на найменших вхідних даних

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

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

Що з наведеного зростає найповільніше зі збільшенням n?

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

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

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

Чому багато бібліотечних процедур сортування переходять на сортування вставками для дуже малих підмасивів?

1. AСортування вставками має малі накладні витрати й швидке на малих або майже відсортованих даних
2. BРекурсивні алгоритми не можуть обробляти масиви менші за 10 елементів
3. CСортування вставками має складність O(n log n) у найгіршому випадку
4. DСортування вставками використовує менше пам'яті, ніж будь-який інший алгоритм сортування, на великих даних

Яке жадібне правило в задачі про вибір заявок (activity selection) завжди дає максимальну кількість заявок, що не перекриваються?

1. AОбрати заявку, що закінчується найраніше, а потім повторити із сумісними
2. BОбрати заявку, що починається найраніше
3. CСпершу обрати заявку з найменшою кількістю перекриттів, а потім повторити із сумісними
4. DСпершу обрати найкоротшу заявку

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

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

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

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