Ну, я хочу использовать Быстрая сортировка по заданным значениям 3, не имеет значения, какие значения, как я могу добраться до наихудшего случая, который является 9 операций?Quicksort, учитывая 3 значения, как я могу получить до 9 операций?
Может кто-нибудь нарисовать дерево и показать, как он показывает nlogn и n^2 операции? Я пытался найти в Интернете, но я до сих пор не смог правильно рисовать, чтобы показать это.
Худший размер сложности быстрого сортировки зависит от выбранного стержня. Если выбранный шарнир является самым левым или самым правым элементом. Тогда наихудшая сложность будет возникать в следующих случаях:
1) Array уже сортирован в том же порядке.
2) Array сортирован в обратном порядке.
3) Все элементы одинаковы (специальный корпус корпуса 1 и 2).
Поскольку эти случаи встречаются очень часто, ось вращения выбирается случайным образом. Выбирая случайный случай, шансы на худший случай уменьшаются.
Анализ алгоритма quicksort объясняется в this blogpost от khan academy.
Я вижу , но как я могу доказать, что с деревом, которое даст 2 операции в хорошем и среднем случае и 9 операций в худшем случае? –
Я нашел сообщение в блоге khan academy, которое объясняет это математически. Я отредактировал свой ответ со своей ссылкой. Вы можете взглянуть на него. –
Я тоже там посмотрел. Это не помогло –
Возможный дубликат [Худший случай для QuickSort - когда это может произойти?] (Http://stackoverflow.com/questions/2415193/worst-case-for-quicksort-when-can-it-occur) – iainn