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

Что такое рекурсия?

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

Каково O большое для 3n² + 5n + 2?

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

Что означает f(n) = Θ(g(n))?

1. Af растёт строго быстрее g
2. Bf растёт с той же скоростью, что g, будучи ограниченной сверху и снизу постоянными кратными g
3. Cf растёт строго медленнее g
4. Df всегда меньше g при любом n, поэтому g ограничивает её сверху, но никогда не снизу

Функция выполняет один цикл из n итераций, а затем, отдельно, ещё один цикл из n итераций. Какова её временна́я сложность?

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

Что вычисляет алгоритм Флойда–Уоршелла и как быстро?

1. AКратчайшие пути между всеми парами вершин за O(V³)
2. BТопологический порядок за O(V²)
3. CМинимальное остовное дерево за O(E log V)
4. DКратчайшие пути из одной исходной вершины до всех остальных за O(V + E)

При монетах 1, 3 и 4 и сумме 6 сколько монет использует жадный метод «сначала самая крупная монета» по сравнению с оптимумом?

1. AЖадный метод использует 4 монеты; оптимум — 3
2. BЖадный метод использует 3 монеты; оптимум — 2
3. CЖадный метод использует 3 монеты; оптимум — 3
4. DЖадный метод использует 2 монеты; оптимум — 2

Проблема остановки показывает, что:

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

Умножение Карацубы удовлетворяет T(n) = 3T(n/2) + O(n). Каково решение?

1. AΘ(n³)
2. BΘ(n²)
3. CΘ(n log n)
4. DΘ(n^{log₂ 3}), примерно n^1,585