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

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

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

Що описує час виконання в середньому випадку?

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

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

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

Жадібний алгоритм:

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

Ви один раз сортуєте масив із n елементів, а потім відповідаєте на k запитів про належність бінарним пошуком. Яка загальна вартість?

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

Приблизно скільки порівнянь потребує бінарний пошук у найгіршому випадку на відсортованому масиві з 1,000,000 елементів?

1. AБлизько 1,000
2. BБлизько 500,000
3. CБлизько 20
4. DБлизько 100

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

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

Яка часова складність побудови бінарної купи з n невідсортованих елементів висхідним методом (bottom-up)?

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