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

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

1. A8 секунд
2. B4 секунды
3. C2 секунды
4. D1 секунду

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

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

Какой класс сложности растёт быстрее всех при больших n?

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

Жадный алгоритм:

1. AИспользует только рекурсию
2. BНа каждом шаге делает локально наилучший выбор
3. CВсегда даёт оптимальное решение
4. DПеребирает все возможные решения

Какова временна́я сложность умножения двух матриц n × n стандартным тройным циклом?

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

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

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

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

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

Что нужно сделать, чтобы показать, что новая задача X NP-трудна?

1. AПоказать, что у X нет полиномиального алгоритма для малых входов
2. BСвести известную NP-трудную задачу к X за полиномиальное время
3. CСвести X к известной NP-трудной задаче за полиномиальное время
4. DПоказать, что X можно проверить за полиномиальное время