#arrays #algorithm #sorting #quicksort
#массивы #алгоритм #сортировка #быстрая сортировка
Вопрос:
Мы хотим выполнить сортировку с помощью стандартной быстрой сортировки, и нам гарантировано, что после вызова метода partition разница в размерах для обоих разделов составляет не более постоянного коэффициента a . Какова наихудшая среда выполнения для этого алгоритма?
Ответ №1:
При ограниченной разнице в размерах между разделами быстрая сортировка является наихудшим вариантом O (n log (n))
По сути, быстрая сортировка проходит по всему массиву каждый раз, когда он выполняет разделение. Поэтому нам нужно учитывать только наихудшее разбиение и сколько разбиений требуется, чтобы уменьшить его до размера 1 (или 2).
Теперь, если нам гарантировано, что больший из двух разделов не более чем в раз больше другого, то в худшем случае больший раздел всегда в раз больше.
В этом случае количество «слоев» в быстрой сортировке будет равно количеству раз, которое мы должны разделить исходный размер массива на (1 a) / a, чтобы получить 1. Это равно логарифму с основанием (1 a) / a от входного размера. Поскольку a является постоянным, то и (1 a) / a , и, следовательно, количество разбиений равно O(log (n)), что означает, что алгоритм выполняется в O(n log (n)) наихудшем случае.