Каково время выполнения быстрой сортировки, если мы выбираем пивот с определенной вероятностью?

Question

Если нам нужно выбрать точку х для быстрой сортировки случайным образом, с вероятностью 0,5, х является медианой;с вероятностью 0,5 х является минимумом.Я понимаю, что время работы при выборе минимального значения равно O (n ^ 2), а время работы при выборе медианного значения равно O (n logn).Если мы объединим их вместе, будет ли общее время работы по-прежнему составлять O (n logn)?

Answer 1

В Corman et. Есть хороший расчет о хорошем и плохом расколе.и др.Когда хорошее разделение, сопровождаемое плохим разделением, время выполнения будет O (nlogn).

Даже, когда разделение происходит все время 10/100, время выполнения будет O (nlogn).

Если ваш вопрос;с вероятностью 1/2 - хорошее разделение, а с вероятностью 1/2 - плохое разделение, ответом будет ожидаемое время выполнения O (nlogn).Потому что всегда есть случай, когда с очень плохой удачей у нас будет плохой раскол.