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

Алгоритм 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Трудноразрешимые задачи нельзя решить никаким алгоритмом, а неразрешимым нужно лишь экспоненциальное время