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

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

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

Що таке базовий випадок рекурсивної функції?

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

Що таке мемоізація?

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

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

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

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

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

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

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

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

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

Чому будь-який пошук порівняннями у відсортованому масиві потребує Ω(log n) порівнянь у найгіршому випадку?

1. AДерево рішень з n можливими результатами має глибину щонайменше log₂ n
2. BКожне порівняння триває логарифмічний час
3. CКожен елемент треба порівняти щонайменше один раз
4. DБінарний пошук — єдиний можливий алгоритм, і йому потрібно log₂ n порівнянь