Будет ли число сравнений отличаются, когда мы берем последний элемент в качестве шарнирного элемента быстрой сортировки и когда мы берем первый элемент в качестве поворотного элемента в быстрой сортировке ??Количества сравнений в быстром изменении рода
Нет, это не будет. В быстром роде, что происходит, мы выбрали элемент поворота (скажем, x). Затем разделите список на 2 части больше x и меньше x.
Следовательно, количество сравнений изменяется незначительно пропорционально глубине рекурсии. Таким образом, чем глубже рекурсивная функция, тем больше будет количество сравнений, чтобы разделить список на 2 части.
глубина рекурсии отличается - больше значение x может делить список на аналогичные длины, меньшим будет глубина рекурсии.
Следовательно, не имеет значения, выбрали ли вы первый или последний элемент в качестве стержня, но может ли это значение разделить список на 2 одинаковых списка длин.
Редактировать Чем больше стержень находится близко к медиане, меньшим будет сложность (O (NlogN)). Чем больше стержень близок к максимальному или минному списку, тем сложнее увеличивается (до O (n^2))
Спасибо! И если мы выберем медианную фигуру, все же сравнения будут одинаковыми? Знаю, что это будет иметь наименьшую глубину. –
@ShubhamGoyal Количество сравнений, очевидно, зависит от входных данных. Но дело в том, что при выборе первого/последнего элемента в качестве поворота вы получили n^2 ops на полностью отсортированном/rev. отсортированные данные, которые на практике случаются довольно часто. Выбирая медиану, вы также можете столкнуться с n^2, но это менее вероятно. – Matt
Когда первый элемент или последний элемент выбраны как ось поворота, количество сравнений остается таким же, но оно является наихудшим случаем, так как массив сортируется или сортируется в обратном порядке. На каждом шаге цифры делятся следующим образом.
T(n) = T(n-1) + O(n) and if you solve this relation it will give you the complexity of theta(n^2)
И когда вы выбираете средний элемент как стержень дает рецидивы отношения
T(n) = 2T(n/2) + \theta(n) which is the best case as it gives complexity of `nlogn`
Можете ли вы быть более конкретным, что ваша проблема программирования? Поделитесь некоторым кодом, возможно. У вас возникли проблемы с добавлением инструментария в ваш алгоритм, чтобы вы могли рассчитывать сравнения? –