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

Яку стратегію проєктування використовує сортування злиттям?

1. AЖадібний вибір
2. B«Розділяй і володарюй»
3. CПовний перебір
4. DДинамічне програмування

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

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

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

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

Який алгоритм сортування є стійким?

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

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

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

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

1. AБлизько n
2. BБлизько √n
3. CБлизько n / 2
4. DБлизько log₂ n

Що треба зробити, щоб показати, що нова задача X є NP-складною?

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

Найкоротші прості шляхи можна знайти за поліноміальний час. Що відомо про пошук найдовшого простого шляху між двома вершинами в загальному графі?

1. AВона нерозв'язна
2. BЦе NP-складна задача
3. CЇї завжди можна розв'язати за O(V + E)
4. DЇї можна розв'язати алгоритмом Дейкстри з від'ємними вагами