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

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

1. A12 секунд
2. B9 секунд
3. C3 секунди
4. D6 секунд

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

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

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

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

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

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

Скільки пам'яті стека використовує проста рекурсивна функція факторіала fact(n) = n × fact(n − 1)?

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

Розв'язком рекурентного співвідношення T(n) = 2T(n/2) + O(n) є:

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

Який час виконання алгоритму Дейкстри з бінарною купою на графі з V вершинами та E ребрами?

1. AO(V + E)
2. BO(V³)
3. CO((V + E) log V)
4. DO(V × E)

Яка різниця між нерозв'язною задачею та практично нерозв'язною?

1. AОбидва терміни означають, що задача взагалі не має алгоритму
2. BНерозв'язні задачі належать до NP, а практично нерозв'язні — до P
3. CДля нерозв'язної задачі немає алгоритму для всіх вхідних даних; для практично нерозв'язної він є, але надто повільний
4. DПрактично нерозв'язні задачі не може розв'язати жоден алгоритм, а нерозв'язні лише потребують експоненційного часу