Быстрые точки разворота

Question

Для быстрой сортировки (в java, если это имеет значение), существует ли связь между количеством точек разворота (или индексов разворота) и размером данного массива?Например, если размер массива равен 10, всегда ли будут, скажем, 5 точек разворота?

Answer 1

Вы можете иметь сколько угодно желающих (до n я полагаю ...)

Чем больше у вас пивотов, тем эффективнее будет следующая рекурсия, хотя, если она будет слишком большой (особенно если бы он был непостоянным) вы потеряли бы больше времени на поиск своего стержня, чем получили бы.

Я считаю, что типичным является 3 потенциальных поворота на итерацию, но это полностью зависит от реализации.

Но помните, что в худшем случае вы получите n итераций (наихудший случай быстрой сортировки - O(n^2)).Естественно, это потребовало бы n стержней, и каждая итерация выполняла бы очень мало работы.

Теперь, на последней итерации, вы можете ожидать около n / 3 стержней.На приведенной выше итерации это будет n / 6.На следующей итерации это будет n / 12.Если вы возьмете предел этой серии, вы получите 0,6 повторения.Похоже, что вы можете ожидать 2/3 n полных опорных точек (потому что у вас будет около 2/3 n полных итераций)

Answer 2

Не обязательно. Это зависит от данных и вашего алгоритма. В среднем с прилично случайными данными и приличной реализацией это должно быть порядка log ₂ (n) опорных точек.

Answer 3

Да, про н / 2 верно. Однако я не знаю, почему это так важно.