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

Яке позначення описує нижню межу зростання?

1. AO (велике O)
2. Bo (мале o)
3. CΩ (велике Омега)
4. DΘ (велике Тета)

Який клас складності зростає найшвидше для великих n?

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

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

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

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

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

Яка часова складність множення двох матриць n × n стандартним потрійним циклом?

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

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

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

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

1. AQuickselect працює за очікуваний час O(n), а метод медіани медіан гарантує O(n) у найгіршому випадку
2. BВибір завжди потребує Ω(n log n), бо вимагає сортування
3. CQuickselect працює за O(log n) у найгіршому випадку, бо рекурсивно переходить лише в один бік від опорного елемента
4. DВибір можливий лише за O(n²)

Яка з цих задач виконуваності, як відомо, розв'язна за поліноміальний час?

1. AЗагальна SAT для формул у кон'юнктивній нормальній формі
2. B3-SAT, де кожен диз'юнкт має рівно три літерали
3. CВиконуваність схем
4. D2-SAT, де кожен диз'юнкт має щонайбільше два літерали