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

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

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

Що означає, що операція виконується за час O(1)?

1. AВона обробляє рівно один елемент за секунду часу виконання
2. BЇї час виконання не зростає з розміром вхідних даних
3. CВона завжди триває рівно одну секунду
4. DЇї можна виконати лише один раз

Який час виконання сортування підрахунком для n цілих чисел у діапазоні від 0 до k?

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

Чому основу логарифма в «великому O» зазвичай не вказують, як-от в O(log n)?

1. AОснова має значення лише для малих n
2. BУсі логарифми в інформатиці мають основу 10, тож вона мається на увазі
3. CЛогарифми з різними основами відрізняються лише сталим множником
4. DЛогарифми завжди округлюють до цілих

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

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

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

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

Яка оцінка для log(n!) правильна?

1. AΘ(n²)
2. BΘ(log n)
3. CΘ(n)
4. DΘ(n log n)

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

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