Чему равна сложность алгоритма быстрой сортировки массива, состоящего из 10 элементов в лучшем, среднем и худшем случаях?
Указания: В ответ введите через пробел три числа, соответствующих лучшему, среднему и худшему случаям.
Пример ввода ответа: 3712
Рассмотрим пошагово, как определить асимптотическую сложность быстрой сортировки для массива из 10 элементов.
В лучшем случае на каждом шаге разделитель (опорный элемент) делит массив почти пополам. В этом случае рекуррентное соотношение имеет вид
T(n) = 2·T(n/2) + O(n).
По теореме о мастере получаем, что T(n) = O(n·log n).
В среднем случае распределение элементов таково, что разделения не всегда идеальные, но в среднем сумма затрат всё равно оказывается пропорциональ...