Алгоритмы и сложность: лист заданий с ответами

Алгоритм O(n) работает 3 секунды при n = 1 миллион. Примерно сколько он будет работать при n = 2 миллиона?

1. A9 секунд
2. B12 секунд
3. C6 секунд
4. D3 секунды

Что такое алгоритм полного перебора (brute force)?

1. AАлгоритм, угадывающий ответ случайным образом
2. BАлгоритм, работающий на многих процессорах
3. CАлгоритм, перебирающий все возможные кандидаты в решения
4. DАлгоритм, который всегда использует рекурсию

Какова временная сложность линейного поиска в неотсортированном массиве из n элементов (в худшем случае)?

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

Примерно сколько сравнений нужно бинарному поиску в худшем случае на отсортированном массиве из 1,000,000 элементов?

1. AОколо 1,000
2. BОколо 500,000
3. CОколо 100
4. DОколо 20

Временная сложность наивного рекурсивного вычисления чисел Фибоначчи (fib(n) = fib(n−1) + fib(n−2)) является:

1. AЭкспоненциальной
2. BЛинейной
3. CЛогарифмической
4. DКонстантной

Каково решение рекуррентного соотношения T(n) = 2T(n − 1) + O(1)?

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

Почему любой поиск в отсортированном массиве, основанный на сравнениях, требует в худшем случае Ω(log n) сравнений?

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

Каковы затраты времени и памяти при вычислении n-го числа Фибоначчи циклом, хранящим только два последних значения?

1. AO(n) времени и O(n) памяти
2. BO(log n) времени и O(n) памяти
3. CO(n) времени и O(1) памяти
4. DO(2ⁿ) времени и O(1) памяти