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

Які три кроки алгоритму «розділяй і володарюй»?

1. AРозділити, підкорити, об'єднати
2. BПрочитати, обчислити, записати
3. CВгадати, перевірити, повторити
4. DВідсортувати, знайти, повернути

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

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

Скільки додаткової пам'яті використовує стандартне сортування злиттям на основі масиву?

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

Що обчислює алгоритм Флойда–Воршелла і як швидко?

1. AМінімальне кістякове дерево за O(E log V)
2. BТопологічний порядок за O(V²)
3. CНайкоротші шляхи від однієї початкової вершини до всіх інших за O(V + E)
4. DНайкоротші шляхи між усіма парами вершин за O(V³)

Часова складність наївного рекурсивного обчислення чисел Фібоначчі (fib(n) = fib(n−1) + fib(n−2)) є:

1. AЛінійною
2. BСталою
3. CЕкспоненційною
4. DЛогарифмічною

Чому динамічне програмування не дає реального пришвидшення для сортування злиттям?

1. AСортування злиттям уже має складність O(n)
2. BСортування злиттям не має рекурсивної структури
3. CДинамічне програмування працює лише на задачах про графи, а не на масивах
4. DЙого підзадачі не перекриваються, тож нічого використати повторно

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

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

Алгоритм динамічного програмування Гелда–Карпа точно розв'язує задачу комівояжера. Який його час виконання для n міст?

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