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

Що описує час виконання алгоритму в найгіршому випадку?

1. AОчікуваний час на випадкових вхідних даних розміру n
2. BЧас на найменших вхідних даних
3. CМаксимальний час на всіх вхідних даних розміру n
4. DЧас на повільному комп'ютері

Що таке алгоритм?

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

Задачу зазвичай називають практично розв'язною (tractable), якщо:

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

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

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

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

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

Маючи монети номіналом 1, 3 і 4 та суму 6, скільки монет використовує жадібний метод «спершу найбільша монета» порівняно з оптимумом?

1. AЖадібний використовує 2 монети; оптимум — 2
2. BЖадібний використовує 3 монети; оптимум — 3
3. CЖадібний використовує 3 монети; оптимум — 2
4. DЖадібний використовує 4 монети; оптимум — 3

Топологічне сортування можливе лише для:

1. AНеорієнтованих графів
2. BОрієнтованих ациклічних графів
3. CПовних графів
4. DГрафів із від'ємними вагами

Чому пошук у геш-таблиці в середньому має складність O(1), а в найгіршому випадку — O(n)?

1. AГеш-функції повільні
2. BБагато ключів через колізії можуть потрапити в один і той самий кошик
3. CДоступ до масивів має складність O(n)
4. DКлючі спершу потрібно відсортувати