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

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

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

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

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

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

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

Быстрая сортировка всегда берёт в качестве опорного первый элемент. На каком входе проявляется её поведение в худшем случае?

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

Нижняя граница для сортировки сравнениями в худшем случае равна:

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

Верно ли утверждать, что алгоритм O(n²) также является O(n³)?

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

Каковы затраты времени и памяти при вычислении n-го числа Фибоначчи циклом, хранящим только два последних значения?

1. AO(n) времени и O(1) памяти
2. BO(2ⁿ) времени и O(1) памяти
3. CO(log n) времени и O(n) памяти
4. DO(n) времени и O(n) памяти

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

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