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

Чому дорівнює log₂ 1024?

1. A512
2. B10
3. C32
4. D12

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

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

Алгоритм O(n²) працює 1 секунду для n = 1000. Приблизно скільки він працюватиме для n = 2000?

1. A8 секунд
2. B2 секунди
3. C1 секунду
4. D4 секунди

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

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

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

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

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

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

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

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

Проблема зупинки показує, що:

1. AЖоден алгоритм не може для кожної програми та вхідних даних визначити, чи зупиниться вона
2. BДеякі програми працюють швидше на швидших комп'ютерах, тож зупинка залежить від апаратного забезпечення
3. CКожна програма врешті-решт зупиняється
4. DСлід уникати циклів