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

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

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

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

1. A9 секунд
2. B3 секунди
3. C12 секунд
4. D6 секунд

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

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

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

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

Яке твердження про рекурсивну функцію без досяжного базового випадку правильне?

1. AВона автоматично повертає 0
2. BВона викликає себе, доки не переповниться стек викликів
3. CВона виконується за час O(1)
4. DКомпілятор завжди перетворює її на цикл, що безпечно завершується

Функція виконує один цикл із n ітерацій, а потім окремо ще один цикл із n ітерацій. Яка її часова складність?

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

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

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

За основною теоремою (master theorem) розв'язком T(n) = 8T(n/2) + O(n²) є:

1. AΘ(n²)
2. BΘ(n³)
3. CΘ(n log n)
4. DΘ(n² log n)