Быстрая сортировка (in-place) в среднем работает за время O(n log n). По дополнительной памяти она использует стек вызовов рекурсии, глубина которого в среднем составляет O(log n). Таким образом, средние асимптотики:
Укажите средние асимптотики времени и доп. памяти для быстрой сортировки (in-place) при сортировке слайса из n элементов
Быстрая сортировка (in-place) в среднем работает за время O(n log n). По дополнительной памяти она использует стек вызовов рекурсии, глубина которого в среднем составляет O(log n). Таким образом, средние асимптотики:
Короткий ответ
Что ответить на собеседовании
Подробный разбор
Ответ с пояснениями
Условие
Укажите средние асимптотики времени и доп. памяти для быстрой сортировки (in-place) при сортировке слайса из n элементов
O(n log n) по времени, O(log n) по памяти стека
O(n log n) по времени, O(1) по памяти
O(n^2) по времени, O(log n) по памяти стека
O(n log n) по времени, O(n) по памяти
Ответ
Быстрая сортировка (in-place) в среднем работает за время O(n log n). По дополнительной памяти она использует стек вызовов рекурсии, глубина которого в среднем составляет O(log n). Таким образом, средние асимптотики:
- Время: O(n log n)
- Дополнительная память: O(log n) (за счет стека вызовов)
Пример из вариантов:
O(n log n) по времени, O(log n) по памяти стека
Это корректный ответ. Другие варианты либо неверны по времени, либо по памяти.