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

Что описывает время работы алгоритма в худшем случае?

1. AОжидаемое время на случайном входе размера n
2. BМаксимальное время по всем входам размера n
3. CВремя на медленном компьютере
4. DВремя на самом маленьком входе

Что описывает время работы в среднем случае?

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

Что такое мемоизация?

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

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

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

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

1. AO(mn)
2. BO(m + n)
3. CO(2^m+n)
4. DO(mn log n)

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

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

Какой приём обеспечивает ожидаемое время работы O(n log n) для быстрой сортировки на любых входных данных?

1. AВыбор опорного элемента случайно с равномерным распределением
2. BСортировка входных данных перед запуском быстрой сортировки
3. CВыбор всегда первого элемента
4. DПрименение рекурсии только к левой части

Принадлежит ли 2²ⁿ классу O(2ⁿ)?

1. AНет, потому что 2²ⁿ = 4ⁿ, а 4ⁿ / 2ⁿ = 2ⁿ растёт неограниченно
2. BНет, потому что 2²ⁿ растёт медленнее 2ⁿ
3. CДа, потому что обе функции экспоненциальны
4. DДа, потому что постоянные множители в показателе в O большом всегда игнорируются