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

Какова временна́я сложность поиска наибольшего значения в неотсортированном массиве из n чисел?

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

Доступ к элементу массива по индексу занимает:

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

Какова временна́я сложность поиска в глубину на графе, хранящемся в виде списков смежности?

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

Сколько уровней у рекурсии сортировки слиянием для массива из n элементов?

1. AОколо n / 2
2. BОколо √n
3. CОколо n
4. DОколо log₂ n

Какой алгоритм находит кратчайшие пути из одного источника в графе с неотрицательными весами рёбер?

1. AАлгоритм Дейкстры
2. BВо всех случаях требуется алгоритм Беллмана–Форда
3. CПоиск в глубину (DFS)
4. DАлгоритм Краскала

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

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

По основной теореме (master theorem) решением T(n) = 8T(n/2) + O(n²) является:

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

Почему бинарный поиск не даёт времени O(log n) на односвязном списке?

1. AСравнения узлов связного списка медленнее
2. BЧтобы добраться до среднего элемента, нужно O(n) шагов, поскольку нет прямого доступа по индексу
3. CСвязные списки нельзя сортировать
4. DБинарному поиску нужно как минимум вдвое больше памяти