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

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

1. A12 секунд
2. B6 секунд
3. C3 секунды
4. D9 секунд

Чему равен log₂ 1024?

1. A12
2. B32
3. C10
4. D512

Какова временна́я сложность сортировки вставками в лучшем случае, на уже отсортированном массиве?

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

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

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

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

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

Что измеряет амортизационный анализ?

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

Почему поиск в хеш-таблице в среднем имеет сложность O(1), а в худшем случае — O(n)?

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

Какова амортизированная стоимость инкремента двоичного счётчика, если один инкремент может изменить много битов?

1. AO(log n) на инкремент
2. BO(1) на инкремент
3. CO(n) на инкремент
4. DO(n log n) на инкремент