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

Чего бинарный поиск требует от входных данных?

1. AМассив должен быть отсортирован
2. BМассив должен содержать только положительные числа
3. CДлина массива должна быть степенью двойки
4. DВ массиве должно быть не более 1000 элементов

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

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

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

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

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

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

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

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

Каково время работы поразрядной сортировки LSD для n целых чисел из d цифр в системе счисления с основанием k?

1. AO(n²)
2. BO(dn log k)
3. CO(d(n + k))
4. DO(n log n)

Как соотносятся n! и 2ⁿ при больших n?

1. An! растёт быстрее 2ⁿ
2. Bn! есть O(n²)
3. C2ⁿ растёт быстрее n!
4. DОни растут с одинаковой скоростью

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

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