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