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

Який із цих часів виконання є поліноміальним?

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

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

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

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

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

Що означає, що задача має оптимальну підструктуру?

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

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

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

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

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

Чому будь-який пошук порівняннями у відсортованому масиві потребує Ω(log n) порівнянь у найгіршому випадку?

1. AКожен елемент треба порівняти щонайменше один раз
2. BБінарний пошук — єдиний можливий алгоритм, і йому потрібно log₂ n порівнянь
3. CДерево рішень з n можливими результатами має глибину щонайменше log₂ n
4. DКожне порівняння триває логарифмічний час

Що випливало б, якби хтось знайшов поліноміальний алгоритм для однієї NP-повної задачі?

1. AКожну задачу з NP можна було б розв'язати за поліноміальний час, тож P = NP
2. BУсі алгоритми з експоненційним часом негайно стали б працювати за лінійний час
3. CПроблема зупинки стала б розв'язною
4. DЛише ця одна задача перейшла б до P